The topological-graph-theory tag has no wiki summary.
5
votes
1answer
121 views
Equivalent embeddings of a graph
I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent.
Intuitively I mean by equivalent that the embeddings look the same up to ...
10
votes
2answers
194 views
Approximability of the genus problem
What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an ...
3
votes
0answers
35 views
Polyhedral embedding from graph degree sequence
Given: A degree sequence.
Wanted: A graph and a polyhedral embedding of this graph (described by a rotation system or something equivalent). By polyhedral embedding I mean only the combinatorial ...
5
votes
1answer
135 views
Face-walks in rotation systems for graphs
Given a graph $G$, a rotation system for $G$ is composed of two elements:
$\pi = \{\pi_v: v\in V(G)\}$, where $\pi_v$ is a cyclic permutation of the edges incident on $v$. Thus if $e$ is an edge ...
2
votes
1answer
65 views
Is the dual of a polyhedral embedding a polyhedral embedding?
A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common ...
6
votes
1answer
135 views
Algorithm to find a polyhedral embedding
A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common ...
4
votes
1answer
155 views
Finding a simple dual of a simple graph in some surface
Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph ...
8
votes
1answer
288 views
Finding a dual of a graph
According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ ...
8
votes
1answer
110 views
Does a pair of disjoint homotopic cycles in the dual separate the graph?
Let $G$ be a graph embedded on an orientable compact surface of genus $g$ so that the embedding is cellular. Consider the dual of the graph $G^*$. Let $C_1$ and $C_2$ be disjoint cycles in $G^*$ that ...
5
votes
1answer
254 views
Place n points in a box as far away from each other as possible
Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized.
In other words, I'm ...
5
votes
2answers
317 views
Is there any good and free Introduction to topological graph theory
My knowledge in topological graph theory is in low, I need some good reference which has two simple thing, Definition of new concepts (like genus,graph embedding in surface, ...) also contains related ...
