Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
On Graphs Supported by Line Sets
verfasst von : Vida Dujmović, William Evans, Stephen Kobourov, Giuseppe Liotta, Christophe Weibel, Stephen Wismath
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For a set
S
of
n
lines labeled from 1 to
n
, we say that
S
supports an
n
-vertex planar graph
G
if for every labeling from 1 to
n
of its vertices,
G
has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of
n
parallel lines supports all
n
-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more “powerful” than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of
n
lines that intersect in a common point supports all
n
-vertex planar graphs. Finally, we show that there exists a set of
n
lines in general position that does not support all
n
-vertex planar graphs.