The tag has no wiki summary.

learn more… | top users | synonyms

9
votes
3answers
171 views

Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology. Are there any applications for these subjects in computer science? I have looked a bit, and ...
1
vote
0answers
87 views

Example of non-disk bounding planarly nested sequences of cycles

I am trying to find an example for the Theorem 5.1 of the paper "Combinatorial Local Planarity and the Width of Graph Embeddings" that can be found at ...
4
votes
1answer
122 views

Addding edges to spanning tree without destroying planarity

Given a graph $G=(V,E)$ with n vertices, m edges, and the maximum degree $\Delta$. Let $T$ be a spanning tree of $G$. Let $E_c \subseteq E - E(T)$ be the maximum number of edges that we can add to $T$ ...
0
votes
0answers
40 views

Graph generation model effect on performance of Spectral graph algorithms

I use spectral graph algorithms for finding community structures, specifically the Leading Eigenvector Method (http://arxiv.org/abs/physics/0605087). I try analyzing the performance of these ...
-1
votes
1answer
209 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
147 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
153 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
134 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
210 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
214 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
71 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
158 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
186 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
497 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
139 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
302 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 ...
4
votes
2answers
454 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 ...