Talk:Planar straight-line graph

From Wikipedia, the free encyclopedia

I deleted from the Problem section that two PLGS can be drawn simultaniously, because it is shown by Brass et al. that two path can be drawn simultaniously, Kaufmann et al. showed that a Tree with it self is selfintersecting and a Tree with a Path is selfintersecting.

Markus Geyer, Michael Kaufmann, Imrich Vrto "Two trees are self-intersecting when drawn simultaniously. Markus Geyer, Michael Kaufmann, Daniel Neuwirth "A path and a tree are self intersecting when drawn simultaniously. Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Koburov, Lubiw, Mitchell, On Simultaneous Graph Embeddings.

That's a very different problem. In the papers you reference, one is given a pair of abstract graphs which should be simultaneously embedded with straight lines in the plane by choosing vertex locations. In the problem you deleted, one is given two maps with vertex locations already fixed (say one map of streets and another of waterways in the same physical locations), and must determine the locations of any crossings. So I'll be undeleting the problem. —David Eppstein (talk) 20:17, 16 March 2008 (UTC)