TY - GEN
T1 - A characterization of planar graphs by pseudo-line arrangements
AU - Tamaki, Hisao
AU - Tokuyama, Takeshi
PY - 1997
Y1 - 1997
N2 - Let G be an arrangement of pseudo-lines, i.e., a collection of unbounded x-monotone curves in which each curve crosses each of the others exactly once. A pseudo-line graph (G, E) is a graph for which the vertices are the pseudo-lines of G and the edges are some un-ordered pairs of pseudo-lines of G. A diamond of pseudo-line graph (G, E) is a pair of edges {p, q}, {pʹ, qʹ} ϵ E, {p, q} Ç {pʹ, qʹ} = ø, such that the crossing point of the pseudo-lines p and q lies vertically between pʹ and qʹ and the crossing point of pʹ and qʹ lies vertically between p and q. We show that a graph is planar if and only if it is isomorphic to a diamond-free pseudo-line graph. An immediate consequence of this theorem is that the O(kl/3n) upper bound on the k-level complexity of an arrangement of straightfines, which is very recently discovered by Dey, holds for an arrangement of pseudo-lines as well.
AB - Let G be an arrangement of pseudo-lines, i.e., a collection of unbounded x-monotone curves in which each curve crosses each of the others exactly once. A pseudo-line graph (G, E) is a graph for which the vertices are the pseudo-lines of G and the edges are some un-ordered pairs of pseudo-lines of G. A diamond of pseudo-line graph (G, E) is a pair of edges {p, q}, {pʹ, qʹ} ϵ E, {p, q} Ç {pʹ, qʹ} = ø, such that the crossing point of the pseudo-lines p and q lies vertically between pʹ and qʹ and the crossing point of pʹ and qʹ lies vertically between p and q. We show that a graph is planar if and only if it is isomorphic to a diamond-free pseudo-line graph. An immediate consequence of this theorem is that the O(kl/3n) upper bound on the k-level complexity of an arrangement of straightfines, which is very recently discovered by Dey, holds for an arrangement of pseudo-lines as well.
UR - http://www.scopus.com/inward/record.url?scp=21944439637&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=21944439637&partnerID=8YFLogxK
U2 - 10.1007/3-540-63890-3_16
DO - 10.1007/3-540-63890-3_16
M3 - Conference contribution
AN - SCOPUS:21944439637
SN - 3540638903
SN - 9783540638902
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 133
EP - 142
BT - Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings
A2 - Leong, Hon Wai
A2 - Jain, Sanjay
A2 - Imai, Hiroshi
PB - Springer Verlag
T2 - 8th Annual International Symposium on Algorithms and Computation, ISAAC 1997
Y2 - 17 December 1997 through 19 December 1997
ER -