# Tagged Questions

The tag has no usage guidance.

256 views

### Minor closed properties that are explicitly MSO expressible

Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications. Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and Seymour'...
288 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 ...
99 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 http://www.fmf.uni-lj.si/~mohar/Reprints/1992/...
128 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$ ...
347 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 ...
179 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 ...
196 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 ...
139 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 ...
215 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 $n^\epsilon$-...
39 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 ...
243 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 ...
76 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 edge,...
169 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 edge,...
192 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 ...
563 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$ ...
144 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 ...