Triangle-free planar graphs as segments intersection graphs

DOI10.1007/3-540-46648-7_35MaRDI QIDQ4501713zbMATH OpenFDO

Authors Natalia de Castro, Francisco Javier Cobos, Juan Carlos Dana, Marc Noy, A. Márquez

Publication date 4 September 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46648-7_35

zbMATH Keywords

triangle-free planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

The authors show that every triangle-free planar graph is the intersection graph of a set of segments in the plane where the segments can be chosen in only three directions (horizontal, vertical and oblique). An intersection graph has a vertex for every segment and two vertices are adjacent if the corresponding segments intersect. For the entire collection see [Zbl 0931.00046].

Recommendations

• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Triangle-free geometric intersection graphs with no large independent sets
• scientific article; zbMATH DE number 6850320
• scientific article; zbMATH DE number 739017
• On the triangle graph of a \(K(1,2,3)\)-free maximal planar graph

Cited in

(17)

• Intersection graphs of halflines and halfplanes
• On contact graphs of paths on a grid
• Not all graphs are segment \(T\)-graphs
• An intersection graph of straight lines
• On some special classes of contact \(B_0\)-VPG graphs
• Finding geometric representations of apex graphs is NP-hard
• Characterising circular-arc contact \(B_0\)-VPG graphs
• Triangle-free geometric intersection graphs with no large independent sets
• 3-colorable planar graphs have an intersection segment representation using 3 slopes
• Packing \([1, \Delta ]\)-factors in graphs of small degree
• Intersection graphs of L-shapes and segments in the plane
• On Representation of Planar Graphs by Segments
• Vertex-arboricity of planar graphs without intersecting triangles
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• Not all planar graphs are in PURE-4-DIR
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Finding geometric representations of apex graphs is \textsf{NP}-hard

This page was built for publication: Triangle-free planar graphs as segments intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4501713)