检索结果-内蒙古大学图书馆

intersection graphs of L-shapes and segments in the plane

DISCRETE APPLIED MATHEMATICS 2016年 206卷 48-55页

作者： Felsner, Stefan Knauer, Kolja Mertzios, George B. Ueckerdt, Torsten Tech Univ Berlin Inst Math Berlin Germany Univ Aix Marseille CNRS LIF UMR 7279 Marseille France Univ Durham Sch Engn & Comp Sci Durham DH1 3HP England Karlsruhe Inst Technol Dept Math D-76021 Karlsruhe Germany

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: left perpenticular, inverted right perpenticular, right perpenticular, and inverted left perpenticular. A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an left perpenticular, an left perpenticular or inverted right perpenticular, a k-bend path, or a segment, then this graph is called an {left perpenticular}-graph, {left perpenticular, inverted right perpenticular}-graph, B-k-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {left perpenticular, inverted right perpenticular}-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are {left perpenticular}-graphs, or B-k-VPG-graphs for some small constant k. We show that all planar 3-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are {left perpenticular}-graphs. Furthermore we show that complements of planar graphs are B-17-VPG-graphs and complements of full subdivisions are B-2-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once. (C) 2016 Elsevier B.V. All rights reserved.

关键词： intersection graphs Segment graphs Co-planar graphs k-bend VPG-graphs Planar 3-trees

来源：评论

学校读者我要写书评

暂无评论

intersection graphs for string links

引用

JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS 2006年第1期15卷 53-72页

作者： Mellor, B Loyola Marymount Univ Dept Math Los Angeles CA 90045 USA

We extend the notion of intersection graphs for chord diagrams in the theory of finite type knot invariants to chord diagrams for string links. We use our definition to develop weight systems for string links via the adjacency matrix of the intersection graphs, and show that these weight systems are related to the weight systems induced by the Conway and Homfly polynomials.

关键词： string links finite type invariants intersection graphs weight systems

来源：评论

学校读者我要写书评

暂无评论

intersection graphs of subgroups of finite groups

引用

CZECHOSLOVAK MATHEMATICAL JOURNAL 2010年第4期60卷 945-950页

作者： Shen, Rulin Hubei Univ Nationalities Dept Math Enshi 445000 Hubei Peoples R China

In this paper we classify finite groups with disconnected intersection graphs of subgroups. This solves a problem posed by Csakany and Pollak.

关键词： intersection graphs finite groups subgroups

来源：评论

学校读者我要写书评

暂无评论

intersection graphs of L-Shapes and Segments in the Plane

Intersection Graphs of L-Shapes and Segments in the Plane

引用

39th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Felsner, Stefan Knauer, Kolja Mertzios, George B. Ueckerdt, Torsten Tech Univ Berlin Inst Math Berlin Germany Univ Montpellier 2 LIRMM F-34095 Montpellier 5 France Univ Durham Sch Engn & Comp Sci Durham DH1 3HP England Karlsruhe Inst Technol Dept Math D-76021 Karlsruhe Germany

ISBN: (纸本)9783662444658;9783662444641

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: left perpendicular, inverted right perpendicular, right perpendicular and inverted left perpendicularL. A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an left perpendicular, an left perpendicular or inverted right perpendicular, a k-bend path, or a segment, then this graph is called an {left perpendicular}-graph, {left perpendicular, inverted right perpendicular}-graph, B-k-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer [Discrete Mathematics, 108( 1): 365-372, 1992], stating that every {left perpendicular, inverted right perpendicular}-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are {left perpendicular}-graphs, or Bk-VPG-graphs for some small constant k. We show that all planar 3-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are {left perpendicular}-graphs. Furthermore we show that all complements of planar graphs are B-19-VPG-graphs and all complements of full subdivisions are B-2-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.

关键词： intersection graphs segment graphs co-planar graphs k-bend VPG-graphs planar 3-trees

来源：评论

学校读者我要写书评

暂无评论

The k-edge intersection graphs of paths in a tree

引用

DISCRETE APPLIED MATHEMATICS 2008年第4期156卷 451-461页

作者： Golumbic, Martin Charles Lipshteyn, Marina Stern, Michal Univ Haifa Caesarea Rothschild Inst IL-31999 Haifa Israel Acad Coll Tel Aviv Jaffa Tel Aviv Israel

We consider a generalization of edge intersection graphs of paths in a tree. Let P be a collection of nontrivial simple paths in a tree T. We define the k-edge (k >= 1) intersection graph Gamma(k) (P), whose vertices correspond to the members of P, and two vertices are joined by an edge if the corresponding members of P share k edges in T. An undirected graph G is called a k-edge intersection graph of paths in a tree, and denoted by k-EPT, if G = Gamma(k)(P) for some P and T. It is known that the recognition and the coloring of the 1-EPT graphs are NP-complete. We extend this result and prove that the recognition and the coloring of the k-EPT graphs are NP-complete for any fixed k >= 1. We show that the problem of finding the largest clique on k-EPT graphs is polynomial, as was the case for 1-EPT graphs, and determine that there are at most O(n(3)) maximal cliques in a k-EPT graph on n vertices. We prove that the family of 1-EPT graphs is contained in, but is not equal to, the family of k-EPT graphs for any fixed k >= 2. We also investigate the hierarchical relationships between related classes of graphs, and present an infinite family of graphs that are not k-EPT graphs for every k >= 2. The edge intersection graphs are used in network applications. Scheduling undirected calls in a tree is equivalent to coloring an edge intersection graph of paths in a tree. Also assigning wavelengths to virtual connections in an optical network is equivalent to coloring an edge intersection graph of paths in a tree. (C) 2007 Published by Elsevier B.V.

关键词： paths of a tree intersection graphs EPT-graphs chordal graphs coloring

来源：评论

学校读者我要写书评

暂无评论

Multi-intersection graphs

引用

DISCRETE MATHEMATICS 2000年第1-3期218卷 245-251页

作者： Zverovich, IE Belarusian State Univ Dept Mech & Math Minsk 220050 BELARUS

Let P = P-l be a hereditary class of intersection graphs. For m greater than or equal to 2 denote by P-m the extension of P by admitting up to in copies for any subset (corresponding to a vertex of a graph). Clearly, P-m subset of or equal to Pm+1 for all m greater than or equal to 1. Put P* = boolean OR P-m over all m greater than or equal to 1. We introduce a method for constructing forbidden induced subgraphs (FIS) for P-m (m greater than or equal to 2) and P* provided that the FIS characterization for P-l is known. We apply the method to line graphs of multigraphs with/without bounded edge multiplicities. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： intersection graphs hereditary properties forbidden induced subgraphs

来源：评论

学校读者我要写书评

暂无评论

Representing edge intersection graphs of paths on degree 4 trees

引用

DISCRETE MATHEMATICS 2008年第8期308卷 1381-1387页

作者： Golumbic, Martin Charles Lipshteyn, Marina Stern, Michal Univ Haifa Caesarea Rothschild Inst IL-31999 Haifa Israel Acad Coll Tel Aviv Tel Aviv Israel

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G = EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph. An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement (G) over bar possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs. (C) 2007 Elsevier B.V. All rights reserved.

关键词： paths of a tree intersection graphs weakly chordal graphs EPT graphs coloring

来源：评论

学校读者我要写书评

暂无评论

Clique-Based Separators for Geometric intersection graphs

引用

ALGORITHMICA 2023年第6期85卷 1652-1678页

作者： de Berg, Mark Kisfaludi-Bak, Sandor Monemizadeh, Morteza Theocharous, Leonidas TU Eindhoven Dept Comp Sci Eindhoven Netherlands Aalto Univ Dept Comp Sci Espoo Finland

Let F be a set of n objects in the plane and let G(x) (F) be its intersection graph. A balanced clique-based separator of G(x) (F) is a set S consisting of cliques whose removal partitions G(x) (F) into components of size at most delta n, for some fixed constant delta < 1. The weight of a clique-based separator is defined as Sigma(C is an element of S) log(vertical bar C vertical bar + 1). Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then G(x) (F) admits a balanced clique-based separator of weight O(root n). We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight O(root n), which is tight in the worst case. (ii) intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n(2/)(3) log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(root n log n). (iii) intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n(2/)(3) log n). (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(root n + r log(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for MAXIMUM INDEPENDENT SET (and, hence, VERTEX COVER), for FEEDBACK VERTEX SET, and for q-COLORING for constant q in these graph classes.

关键词： Computational geometry intersection graphs Separator theorems

来源：评论

学校读者我要写书评

暂无评论

Colouring triangle-free intersection graphs of boxes on the plane

引用

DISCRETE MATHEMATICS 2000年第1-3期220卷 243-249页

作者： Kostochka, AV Perepelitsa, IG Novosibirsk State Univ Novosibirsk 630090 Russia Inst Math Novosibirsk 630090 Russia

We prove that intersection graphs of boxes on the plane with girth 6 and 8 are 3- and 2-degenerate, respectively. This implies that these graphs are 4- and 3-list-colourable, respectively. (C) 2000 Published by Elsevi... 详细信息

关键词： colouring intersection graphs maximum average degree

来源：评论

学校读者我要写书评

暂无评论

Edge intersection graphs of Single Bend Paths on a Grid

引用

NETWORKS 2009年第3期54卷 130-138页

作者： Golumbic, Martin Charles Lipshteyn, Marina Stern, Michal Univ Haifa Caesarea Rothschild Inst IL-31999 Haifa Israel Acad Coll Tel Aviv Yaffo Tel Aviv Israel

We combine the known notion of the edge intersection graphs of paths in a tree with a VLSI grid layout model to introduce the edge intersection graphs of paths on a grid. Let P be a collection of nontrivial simple paths on a grid G. We define the edge intersection graph EPG(P) of P to have vertices which correspond to the members of P, such that two vertices are adjacent in EPG(P) if the corresponding paths in P share an edge in g. An undirected graph G is called an edge intersection graph of paths on a grid (EPG) if G = EPG(P) for some P and G, and (P, G) is an EPG representation of G. We prove that every graph is an EPG graph. A turn of a path at a grid point is called a bend. We consider here EPG representations in which every path has at most a single bend, called B-1-EPG representations and the corresponding graphs are called B-1-EPG graphs. We prove that any tree is a B-1-EPG graph. Moreover, we give a structural property that enables one to generate non B-1-EPG graphs. Furthermore, we characterize the representation of cliques and chordless 4-cycles in B-1-EPG graphs. We also prove that single bend paths on a grid have Strong Helly number 3. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(3),130-138 2009

关键词： intersection graphs paths on a grid path bend

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：