Talk:Planar straight-line graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Discrete mathematics

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)