Every planar graph is the intersection graph of segments in the plane
Authors:
Open Access
- 31 May 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 631-638
Abstract
Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.Keywords
This publication has 11 references indexed in Scilit:
- A planar linear hypergraph whose edges cannot be represented as straight line segmentsEuropean Journal of Combinatorics, 2009
- Representations by Contact and Intersection of SegmentsAlgorithmica, 2007
- Triangle-Free Planar Graphs and Segment Intersection GraphsJournal of Graph Algorithms and Applications, 2002
- Crossing Patterns of SegmentsJournal of Combinatorial Theory, Series A, 2001
- A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segmentsInformation Processing Letters, 1998
- Intersection Graphs of SegmentsJournal of Combinatorial Theory, Series B, 1994
- String graphs. II. recognizing string graphs is NP-hardJournal of Combinatorial Theory, Series B, 1991
- On grid intersection graphsDiscrete Mathematics, 1991
- Intersection graphs of curves in the planeJournal of Combinatorial Theory, Series B, 1976
- A Theorem on GraphsAnnals of Mathematics, 1931