Jump to ContentJump to Main Navigation
The Fascinating World of Graph Theory$
Users without a subscription are not able to see the full content.

Ping Zhang, Gary Chartrand, and Arthur Benjamin

Print publication date: 2017

Print ISBN-13: 9780691175638

Published to Princeton Scholarship Online: May 2018

DOI: 10.23943/princeton/9780691175638.001.0001

Show Summary Details
Page of

PRINTED FROM PRINCETON SCHOLARSHIP ONLINE (www.princeton.universitypressscholarship.com). (c) Copyright Princeton University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use.date: 08 March 2021

Drawing Graphs

Drawing Graphs

(p.183) 10 Drawing Graphs
The Fascinating World of Graph Theory

Arthur Benjamin

Gary Chartrand

Ping Zhang

Princeton University Press

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.