<p>I am not working in graph theory, but I am looking for a reference for the following. I have two vertex colored graphs, each with |V| vertices. Their valence and color valence are bounded by the same constant d. They are embedded in a plane without any crossings (as planar graphs). I would like to say that comparing their plane embeddings up to isotopy that preserves colors has polynomial complexity. I think it must be known to those who work in complexity and topological graph theory, but I cannot find a reference.</p>
<p>I found the following: (1) Babai-Luks proposition about canonization of colored graphs of bounded color valence: the complexity is polynomial, as |V|^P(d) (their paper ``Canonical labeling of graphs&quot;) ; (2) a question and answers about isotopy of graphs in the plane if the graphs are known to be isomorphic: <a href="https://cstheory.stackexchange.com/questions/41546/complexity-of-isotopy-of-embedded-graphs">Complexity of isotopy of embedded graphs</a></p>
<p>If there is no reference for my question, what is the best way to piece (1) and (2) together rigorously and concisely? Some colored graph isomorphisms might give rise to isotopic plane embeddings that preserve colors, and some might not, so the number of such isomorphisms seems important to connect these two results. Alternatively, may be there is extra information in the canonical form that helps here. Or is there another, better way to think about this?</p>

CC BY-SA 4.0
2024-11-27T04:22:42.473Z
The first answer at the other question you linked reduced to the 3-connected case where the embedding (colored or not) is essentially unique.
Joshua Grochow
CC BY-SA 4.0
2024-11-27T16:55:42.017Z
Thank you, I also thought that this was the most promising route. But I wonder about the details: have they ever been written? There are some details I'd like to see: for example, my understanding is that a tree needs to be rooted to have a unique plane embedding. Maybe there are different ways to choose a root for the tree obtained from bi-connected components, and maybe I would then have to check if the coloring is preserved for each, perhaps changing the complexity of this step from linear to polynomial.
AnT
<cc.complexity-theory><reference-request><graph-theory><topological-graph-theory>
Complexity of isotopy of embedded vertex colored graphs
AnT
# Complexity of isotopy of embedded vertex colored graphs

(Asked by: username_0 on 2024-11-27)

I am not working in graph theory, but I am looking for a reference for the following. I have two vertex colored graphs, each with |V| vertices. Their valence and color valence are bounded by the same constant d. They are embedded in a plane without any crossings (as planar graphs). I would like to say that comparing their plane embeddings up to isotopy that preserves colors has polynomial complexity. I think it must be known to those who work in complexity and topological graph theory, but I cannot find a reference.

I found the following: (1) Babai-Luks proposition about canonization of colored graphs of bounded color valence: the complexity is polynomial, as |V|^P(d) (their paper ``Canonical labeling of graphs") ; (2) a question and answers about isotopy of graphs in the plane if the graphs are known to be isomorphic: [Complexity of isotopy of embedded graphs](https://cstheory.stackexchange.com/questions/41546/complexity-of-isotopy-of-embedded-graphs)

If there is no reference for my question, what is the best way to piece (1) and (2) together rigorously and concisely? Some colored graph isomorphisms might give rise to isotopic plane embeddings that preserve colors, and some might not, so the number of such isomorphisms seems important to connect these two results. Alternatively, may be there is extra information in the canonical form that helps here. Or is there another, better way to think about this?

**Tags:** cc.complexity-theory, reference-request, graph-theory, topological-graph-theory
> **Comments:**
> **username_1**: The first answer at the other question you linked reduced to the 3-connected case where the embedding (colored or not) is essentially unique.  
> **username_0**: Thank you, I also thought that this was the most promising route. But I wonder about the details: have they ever been written? There are some details I'd like to see: for example, my understanding is that a tree needs to be rooted to have a unique plane embedding. Maybe there are different ways to choose a root for the tree obtained from bi-connected components, and maybe I would then have to check if the coloring is preserved for each, perhaps changing the complexity of this step from linear to polynomial.  

---

## 0 answers

