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 -