# Tagged Questions

For questions about topological graphs, flows, representation, planar, and book embeddings, geometric graphs, crossing numbers, coloring graphs, and other topics in topological graph theory.

10 views

### What are the properties of non-separating cycle in a genus $g$ surface?

There can be two types of cycle in any genus $g$ surface, separating and non-separating. I know that if the edges of the cycle crosses all the sides of the polygonal schema even number of times then ...
74 views

### Is there a proof that any graph is “drawable” on a 2D surface? [closed]

Are there any theorems that say something formal about the fact that any graph is drawable on a 2D surface, and can be mapped to a 2D array of pixels if the pixels are infinitely small? EDIT: No ...
23 views

### Number of non-isomorphic embeddings.

Define two embeddings of a graph on a surface to be non-isomorphic if their corresponding dual graphs are non-isomorphic. How many distinct embeddings (up to isomorphism) are there of a $3$-regular, ...
35 views

### On combinations of planar graphs of given number of vertices of given valences

Good evening, I am new at the MSE, I signed up just now, so I greet you all; please bare with the newcomer. I have a graph theory problem, which has come up in an entirely different context, a ...
18 views

### Domain of Injectivity of Analytic Map

Suppose we have an analytic map $f: \mathbb{D} \to \mathbb{C}$. Then the set of points where the function is not locally injective is a discrete set. Suppose first for simplicity that the points ...
19 views

### What is the topological interpretation of the girth of a graph?

So we can certainly translate a lot of graph theoretic concept into topological ones, ie) We can use the maximum Euler characteristic of a graph to find the minimal genus of a surface that admits a ...
8 views

### Graph Theory: What is the best kind of network centrality to use to determine flows? sources/sinks?

I am working on a medium-sized (80 vertices), cyclic, directed network with commodities being passed around between agents. Its actually stock market data. I would like to determine who of the ...
19 views

### Specific type of Eulerian cycle

Suppose i have a 4-regular planar graph, and furthermore suppose i pair the 4 edges incident to each vertex, so if $v \in V$ is adjacent to edges $\{e_{1},e_{2},e_{3},e_{4}\}$ i could for example pair ...
34 views

### Find all possible topological-sortings of graph G

A topological ordering of G is an ordering of the nodes as $v_1,v_2,...,v_n$ so that all edges point "forward": for every edge $(v_i,v_j)$, we have $i<j$. Moreover, the first node in a ...
96 views

### What is a “linear chain” in Graph Theory?

What is a linear chain in the context of graphs and trees? For example: a topological sort forms a linear chain What does a linear chain mean in the example above? Another example from ...
23 views

### Does the crossing number of a subgraph give a lower bound for the crossing number of a graph?

I thought of this fairly trivial inequality when thinking about the crossing number of graphs. As the title says, if you find a subgraph with a known crossing number in some graph G (say $Q_4$ for ...
55 views

### Genus and faces of a graph

I am trying to determine the genus of a simple, undirected, connected graph using Euler's formula. However, I'm having trouble computing the number of faces of this graph: I seem to be confused ...
85 views

### Minimal edge cut

Suppose that $C$ is a minimal edge cut of a graph $G=(V,E)$ is it possible that the removal of $C$ can split $G$ into three components? I ask this because i'm reading a proof which states that it's ...
15 views

### Graph embeddings for informational networks

Say we have a fabric of computers (or anything that communicates) all talking to each other in the structure of a graph. If we have a lot of them, we can treat this graph as an approximation to a ...
76 views

### proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
50 views

### Can a chord determine two fundamental circuits in a graph

I was studying fundamental circuits,fundamental cutsets related theorems,then I came across a question in my mind: Is it possible that a chord with respect to a given spanning tree in a graph ...
79 views

### Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
135 views

### NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
43 views

### Graph theory and minor relation

I'm having some confusion with proposition $1.72$ of the Diestal book on Graph Theory which states that (ii) If $\Delta(X) \leq 3$, then every $MX$ contains $TX$ thus every minor with maximum degree ...
56 views

### Cloth cutting algorithm

I have a cloth in 3 dimensions represented as a triangle mesh, which is a kind of spatial graph. The nodes of each triangle are specified in a clockwise manner, such that I can consistently determine ...
36 views

### Topological minor and independence number

If $G$ and $X$ are graphs with $G=TX$, ($X$ is a topological minor of $G$) is there any sort of relation between $\alpha(G)$ and $\alpha(X)$ (the independence numbers of both). In addition if finding ...
115 views

### Examples of non-hamiltonian decomposable graphs

Good Afternoon! I read that Line graph of the Petersen graph is 4-regular 4-edge-connected and non-hamiltonian decomposable. Does someone knows examples (or references) of non-hamiltonian ...
38 views

98 views

### Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
286 views

### k6 embbeding on orientable surface of genus 3 with 6 pentagons faces

I need embbeding K6 on orientable surface of genus 3 . but I was asked to do it with the next stipulation : 5 faces only and all the faces in the embedding will be pentagons . In my opinion the way to ...