All Questions
Tagged with planar-graphs graph-isomorphism
11
questions
0
votes
1
answer
108
views
Planar graphs and isomorphism
If I have a planar graph G and another graph H that's been created by crossing two edges of graph – and its very obviously non-planar. Can I use it as an argument to show that they can not be ...
- 397
0
votes
0
answers
42
views
"Let $G \cong H$. $G$ is planar graph $\Leftrightarrow$ $H$ is planar graph."
"Let $G \cong H$. In this case $G$ is planar graph $\Leftrightarrow$ $H$ is planar graph." If this proposition true, prove that. If false, give an example.
This question in my exercise book. ...
- 13
1
vote
0
answers
739
views
Dual of dual of planar graph $G$ is isomorphic to $G$ if and only if $G$ is connected.
I have been asked to show that the dual of the dual, $(G^*)^*$, of a planar graph $G$ is isomorphic to $G$ if and only if $G$ is connected.
I understand the reasoning in the answer one but that cannot ...
- 103
1
vote
1
answer
78
views
Detecting graph topology.
I have a set of graphs and I need to classify them with respect to their topology. Is there an algorithm which can detect the topology (random, regular, scale-free, etc.) of a given undirected graph?
0
votes
0
answers
105
views
How to determine the number of isomorphic classes of planar graphs that can be obtained as planar duals of a given graph?
How to determine the number of isomorphic classes of planar graphs that can be obtained as planar duals of a given graph?
...
- 101
1
vote
1
answer
572
views
If 2 graphs are isomorphic, are they homeomorphic too?
I'm quite confused about the homeomorphism definition. Vice-versa is definitely not true. But what can we say about the statement:
If 2 graphs are isomorphic, they are homeomorphic .
- 67
2
votes
0
answers
299
views
Automorphism group of planar graphs
I am going through Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. It has shown that the automorphism group of a planar graph $G$ is as follows.
$$
\text{Aut} \left(G\...
- 559
4
votes
1
answer
257
views
when do we say if two graphs are isomorphic and when do we say they are the same?
A complete graph of 4 vertices can be represented with a square and also with a triangle with a vertex in the middle. I'm confused if I should call the two graphs isomorphic or the same?
Also, can ...
- 1,005
2
votes
1
answer
3k
views
Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?
Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph.
Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite.
I know that $G$'s number of faces is ...
- 435
4
votes
1
answer
1k
views
Why is a connected planar graph isomorphic to its double dual?
Let $G^*$ be the dual graph of a planar graph $G$ (see wikipedia article). How does one prove that if $G$ is connected then it is isomorphic to $G^{**}$?
- 840
1
vote
2
answers
409
views
Are these graphs Isomorphic
please consider this two graphes.
G1:
G2:
Are they Isomorphic?
Is G1 a planer graph? It contains a K 3,3 or k5?
thanks alot
- 81