Characteristics of Planar Graphs - University Of Maryland

Characteristics of Planar Graphs - University Of Maryland

Characteristics of Planar Graphs BY: G E O R G E G E M E N T O R: Z AC H A RY G R E E N B E R G What is a graph? Vertices Edges

Variations Weighted Colored (Labeled) Directed http://world.mathigon.org/resources/Graph_Theory/graph.png What is an embedding?

Peterson Graph http://www.imada.sdu.dk/~btoft/GT2009/PetersenGraphEmbeddings_800.gif What is a planar embedding? K4 http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/figs/planar_plane_straight_line.png

Kuratowski Subgraphs K5 K3,3 http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/figs/k_5_and_k_3_3.png

Nonplanarity of K5 and K3,3 CANT ADD RED WITHOUT CROSSING CANT ADD RED OR GRAY WITHOUT CROSSING What is a subdivision?

Kuratowski Subgraphs http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/Diagrams/g83.gif http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/Diagrams/g82.gif Kuratowskis Theorem (1930) A graph is planar if and only if it does not contain a subdivision of K5 or K3,3.

http://www.math.ucla.edu/~mwilliams/pdf/petersen.pdf Minimal Nonplanar Nonplanar graph that becomes planar upon removal of any vertex or edge. If we prove that every minimal nonplanar graph must contain a Kuratowski subgraph then we have proved that every nonplanar graph must contain a Kuratowski

subgraph as all nonplanar graphs must contain a minimal nonplanar subgraph. Connected Graphs https://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29#/media/File:UndirectedDegrees.svg K-Connectivity

2-CONNECTED (BICONNECTED) http://mathworld.wolfram.com/BiconnectedGraph.html 3-CONNECTED WHEEL GRAPHS http://mathworld.wolfram.com/WheelGraph.html

Proof Outline Assume there exists a minimal nonplanar graph without a Kuratowski subgraph. Every minimal nonplanar graph without Kuratowski subgraphs must be 3connected. Every graph that is 3-connected without Kuratowski subgraphs has a planar embedding. Thus every minimal nonplanar graph without a Kuratowski subgraph must have a planar embedding.

CONTRADICTION! Every minimal nonplanar graph is connected. NONPLANAR GRAPH WITH 2 COMPONENTS Other Vertices\ Edges

NON PLANAR Component SMALLER NONPLANAR GRAPH NON

PLANAR Contradicts our Assumption of Minimal Nonplanar Every minimal nonplanar graph is 2-connected. ASSUME THERE IS A CUT-VERTEX

PLANAR EMBEDDING Nonplanar with cut vertex PLANAR PLANAR 4 4

PLANAR Contradicts our Assumption of Minimal Nonplanar The End.

Recently Viewed Presentations

  • Key Terms - PC|MAC

    Key Terms - PC|MAC

    morgueFile. Credit: vahiju. The Job Description. Parenting is a series of related jobs and work experiences (often called a . career) Qualifications include. individual's personal qualities. knowledge of the subject. past experience. Personal Qualities.
  • EMPLOYEE INFORMATIONAL SESSION FAIR LABOR STANDARDS ACT (FLSA)

    EMPLOYEE INFORMATIONAL SESSION FAIR LABOR STANDARDS ACT (FLSA)

    The time is not only hours worked on regular working days during normal working hours but also during corresponding hours on nonworking days. Time spent in travel away from home outside of regular working hours as a passenger on an...
  • Networks II: The OSI Model

    Networks II: The OSI Model

    The Open Systems Interconnection model (OSI model) ... TCP/IP Protocol. TCP is the transport layer protocol. IP is the network layer protocol. Together, they form the primary means of transmission and delivery system in the internet.
  • Ancient India

    Ancient India

    Siddharta was born a Hindu prince or a raja: A prince of India. A priest had predicted that he would become a wandering holy man. To prevent this, his father sheltered him; he did not allow Siddharta to see old...
  • Going for Goals! Keep on learning - SEAL Community

    Going for Goals! Keep on learning - SEAL Community

    Going for Goals/Keep on Learning The SEAL Community * Going for Goals/Keep on Learning The SEAL Community * Scientists have found that people with a positive viewpoint have less stress, better creative problem-solving skills, and better health outcomes than less...
  • Context Clues Using clues in a sentence to

    Context Clues Using clues in a sentence to

    past tense verb. Hydra was a snake with six venomous heads filled with poison. ... The brigand was an imposter. He had dressed up to look like a police officer. Which of the following . best defines the underlined word?...
  • Session 2 - WordPress.com

    Session 2 - WordPress.com

    Session 2 Interpretive Methods ... And since they had no root, they withered away. 7 Other seeds fell among thorns, and the thorns grew up and choked them. 8 Other seeds fell on good soil and produced grain, some a...
  • Presentazione standard di PowerPoint

    Presentazione standard di PowerPoint

    Il Dottore d'Ippona, partendo dalle giovanili posizioni manichee, che forse nel substrato del suo pensiero conserverà a lungo, tratteggia un'analisi sul principio del male il quale costituirà in seguito la base, sia per il pensiero morale di Tommaso, sia per...