Drawing Graphs
Drawing Graphs
This chapter considers the concept of planar graph and its underlying theory. It begins with a discussion of the Three Houses and Three Utilities Problem and how it can be represented by a graph. It shows that solving the Three Houses and Three Utilities Problem is equivalent to the problem of determining whether the graph that represents it can be drawn in the plane without any of its edges crossing. It then describes the Euler Identity and the Euler Polyhedron Formula, along with the proposition that every planar graph contains a vertex of degree 5 or less. It also examines Kuratowski's Theorem, introduced by the Polish topologist Kazimierz Kuratowski, and the problem of crossing number. Finally, it provides an overview of the Art Gallery Problem, Wagner's Conjecture, and the Brick-Factory Problem.
Keywords: planar graph, Three Houses and Three Utilities Problem, Euler Identity, Euler Polyhedron Formula, Kuratowski's Theorem, crossing number, Art Gallery Problem, Wagner's Conjecture, Brick-Factory Problem
Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
Please, subscribe or login to access full text content.
If you think you should have access to this title, please contact your librarian.
To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.
