Questions tagged [planar-graphs]

A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane such that the edges only intersect at vertices. Consider tagging with [tag:combinatorics] and [tag:graph-theory].

491 questions
33 views

Graph planarity definability clarification in literature?

Here it says planarity is definable in first order. http://jgaa.info/accepted/recent/Brandenburg.pdf Here it says planarity testing of graphs is not a first order property. Refer https://simons....
20 views

Planar Eulerian graph

Let G be a planar Eulerian graph. Consider some planar drawing of G. Show that there exists a closed Eulerian tour that never crosses itself in the considered drawing (it may touch itself at vertices ...
44 views

Finding if a subgraph of a minimal non-planar graph is a maximal planar graph

Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal ...
13 views

Outerplanar Graphs with |V| = 2

I am currently working on an assignment for my discrete mathematics lecture. We are currently looking at outerplanar graphs and I am supposed to proof the following. Let G = (V,E) be a outerplanar ...
38 views

How to approach the proof of this formula for triangulations.

I am currently working on an assignment for my discrete mathematics lecture. It is specifically about graphs which are triangulations and have a minimum degree of 3. Triangulation specifically means ...
23 views

28 views

planar graph of Submultiples [duplicate]

There is Graph which is connected with Submultiples. (I am sorry but I don't know what this is called.) For example, 10-node Graph has 10 nodes, 18 edges. node 1 connect all the other nodes. node 2 ...
29 views

Graph Theory Question About Paintings On Walls.

I am faced with the following question for my undergraduate Graph Theory class: Suppose a person is standing in a room which has a painting on each of its walls. Prove that if the room has at most ...
78 views

Finding the number of edges of a triangulation of a polygon on n vertices

I am faced with the following question: A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon and all of whose other faces are triangles. How many edges does a ...
61 views

Can you prove $K_{3,3}$ is not planar without the Jordan Curve Theorem?

The non-planarity of $K_{3,3}$ is well know and e.g. shown here: 3 Utilities | 3 Houses puzzle? However, it is pointed out that the given proofs all use the Jordan Curve Theorem in one form or ...
40 views

23 views

Planar subgraph.

I have to find the greatest planar subgraph of $K_{m,n}$ where $m,n\le3$. So, I know it and i can drow the plane graph with an edge at most $6+2(m-3)$. But I can't show that the graph is the ...
Let G be a simple planar graph on 13 vertices. Prove that at least one of G and its complement G is not planar. Can we say that: e<=3n-6 , where n = number of vertices $n(n-1)/2$ is the total ...