Every planar graph is the intersection graph of segments in the plane

DOI10.1145/1536414.1536500zbMath1304.05115OpenAlexW1979682819MaRDI QIDQ5172758

Jérémie Chalopin, Daniel Gonçalves

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536500

zbMATH Keywords

planar graphsintersection graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Related Items (34)

Intersection graphs of L-shapes and segments in the plane ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Planar graphs have 1-string representations ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ The clique problem in ray intersection graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Parikh word representability of bipartite permutation graphs ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ Segment representation of a subclass of co-planar graphs ⋮ Visibility representations of toroidal and Klein-bottle graphs ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ Coloring triangle-free L-graphs with \(O (\log \log n)\) colors ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ On orthogonal ray trees ⋮ Not all planar graphs are in PURE-4-DIR ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ Stick graphs with length constraints ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ The interval number of a planar graph is at most three ⋮ Counting polygon triangulations is hard ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ On the speed of algebraically defined graph classes ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Subspace intersection graphs ⋮ Unnamed Item ⋮ Recognition and drawing of stick graphs ⋮ Optimality program in segment and string graphs ⋮ Unnamed Item ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ On grounded \(\llcorner\)-graphs and their relatives ⋮ On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance ⋮ Efficient Local Representations of Graphs ⋮ Segment representations with small resolution

This page was built for publication: Every planar graph is the intersection graph of segments in the plane