Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
0answers
29 views

Neural network applied to graph analysis

Having the following undirected graphs: The programmatic representation of a vertex is something like: Vertex { Integer id Vertex[] neighbors } I ...
-1
votes
1answer
139 views

All pairs shortest paths in a DAG [closed]

I have studied the Floyd-Warshall and Johnson algorithms. I am trying to understand if the all pairs shortest paths research in a directed graph G can be implemented in a more efficient way if I ...
2
votes
1answer
107 views

Topological sort with constraints on the relative difference between the vertex labels

A topological sort of a graph $G(V,E)$ consisting of $n$ vertices assigns a label $L(v_x)$ to a vertex $v_x$ where $L$ is defined as $L:V \rightarrow \{1,\dots,n\}$. Let additional constraints over ...
1
vote
1answer
127 views

combinatorical embedding

I have a problem with the following statement : Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G What does this mean ? OK in a spanning tree there ...
5
votes
1answer
131 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
209 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
36 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
195 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
70 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
153 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
181 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
429 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$ ...
9
votes
1answer
135 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
293 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
397 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 ...