Intersection graphs of L-shapes and segments in the plane

DOI10.1016/j.dam.2016.01.028zbMath1335.05046OpenAlexW2569798007MaRDI QIDQ277615

Torsten Ueckerdt, Stefan Felsner, Kolja Knauer, George B. Mertzios

Publication date: 2 May 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.01.028

zbMATH Keywords

intersection graphs\(k\)-bend \(\operatorname{VPG}\)-graphsco-planar graphsplanar 3-treessegment graphs

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

CPG graphs: some structural and hardness results ⋮ On approximating MIS over B1-VPG graphs* ⋮ On dominating set of some subclasses of string graphs ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Coloring triangle-free L-graphs with \(O (\log \log n)\) colors ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ On contact graphs of paths on a grid ⋮ On the speed of algebraically defined graph classes ⋮ Conflict-free coloring of string graphs ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ On some special classes of contact \(B_0\)-VPG graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The clique problem in ray intersection graphs
• Triangle-free geometric intersection graphs with large chromatic number
• Segment representation of a subclass of co-planar graphs
• Straight line triangle representations
• How to draw a planar graph on a grid
• Representations by contact and intersection of segments
• Barycentric systems and stretchability
• A note on visibility graphs
• Degrees of freedom versus dimension for containment orders
• Comparability graphs and intersection graphs
• The max clique problem in classes of string-graphs
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• Edge-intersection graphs of grid paths: the bend-number
• Planar Graphs as VPG-Graphs
• Equilateral L-Contact Graphs
• Intersection Graphs of L-Shapes and Segments in the Plane
• Edge intersection graphs of single bend paths on a grid
• Vertex Intersection Graphs of Paths on a Grid
• Every planar graph is the intersection graph of segments in the plane
• Lower Bounds for Approximation by Nonlinear Manifolds
• Combinatorial and Geometric Properties of Planar Laman Graphs
• Posets and VPG graphs