Questions tagged [topological-graph-theory]

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

0
votes
2answers
43 views

Drawing a graph with given vertices edges and face on genus 1

I want to draw a graph on the genus 1 surface. The graph has 2 vertex, 6 edges and 4 faces hence it by Euler Characteristics formula it lives on genus 1 surface. I want to add an extra condition ...
2
votes
1answer
32 views

3-edge colorable cubic graph with an embedding on an orientable surface that is not 4-face colorable

Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $\mathbb{Z}/2\mathbb{Z} \times \...
2
votes
1answer
42 views

Cycle double cover conjecture for complete graphs?

The cycle double cover conjecture states that for every bridgeless finite $G$ there is a collection of cycles $\mathcal{C}$ in $G$ such that every edges on $G$ occurs in precisely two of the cycles in ...
0
votes
0answers
17 views

Block triangular decomposition of directed graph into strongly connected components

Let $G=(V,E)$ with $E\subseteq V\times V$ be a directed graph with (directed) adjacency matrix $A=A(G)$. I remember having seen a decomposition of $G$ into subgraphs $S_i=(V_i,E_i)$ for $i\in\mathcal ...
0
votes
1answer
75 views

A sufficient condition for planar graph

Let $G$ a graph with $v$ vertices and $e$ edges. Right, I know that if $e>3v-6$ then $G$ is not planar. Do you know any theorem like "If $e<f(v)$ then $G$ is planar"?
0
votes
0answers
82 views

About “combinatorial topology”, what Munkres covers and a textbook reference request

When a university says they research in "combinatorial topology" what does that mean? I've seen a university in Country A list "combinatorial topology" in its math department's research areas, but I ...
1
vote
1answer
30 views

Neighborhoods of a topological graph

Consider a finite connected topological graph $G$ embedded on $\mathbb{R}^2$ with standard topology. Here vertices are points, and each edge is a Jordan arc between vertices; an embedding $e: [0, 1] \...
8
votes
2answers
105 views

Count of maximal sextic toroidal graphs

EDIT: Lots of pictures at Sextic Toroidal Graphs There is one graph on 7 vertices, $K_7$, which is a maximal sextic toroidal graph (genus 1). It can be drawn on a torus with no edges crossing and ...
6
votes
1answer
144 views

Infinite graph is planar iff it can be embedded in sphere

My question is about the following statement about planar graphs: A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$. By an embedding we ...
1
vote
1answer
68 views

Parallel planes of minimal surface

If $S_{1}$ and $S_{2}$ are properly embedded minimal surfaces with free boundary set. If $S_{1}$ does not intersect $S_{2}$ and there exist $p_{1} \in S_{1}$ and $p_{2} \in S_{2}$ such that $dist(S_{...
0
votes
1answer
41 views

How to find an ordering of edges incident on a fixed vertex in a plane embedding?

Suppose that we have a plane embedding $G$. Let $v$ be a vertex in $G$ with degree $d$. There exist an ordering $u_1,u_2,\ldots,u_d$ of neighbors of $v$ such that the graph is still a plane embedding ...
2
votes
0answers
24 views

How many torus can I find as a subgraph of a complete graph?

I am wondering whether there is a way to count how many non-isomorphic torus triangulation given its vertex number. I currently have no clue about how to solve this problem. Can anyone give some ...
0
votes
1answer
31 views

how to show any edges of a closed surface M is on exactly two triangles of M.

I just started to learn a book about surfaces on graph, here is my definition of closed surface: a closed surface is a collection $M$ of triangles (in some Euclidean space) such that (a) $M$ ...
0
votes
1answer
79 views

Minimum genus of torus necessary to embed complete graph $K_n$

You can embed complete graphs $K_1$, $K_2$, $K_3$, and $K_4$ on a genus $0$ torus (a sphere). The minimal genus of a torus on which you can embed $K_5$, $K_6$, and $K_7$ is a $1$. Then you need a ...
0
votes
1answer
17 views

In community detection, can $k$-cliques overlap?

When finding communities in a network using $k$-cliques, each $k$-clique may considered a community. I have an assignment where there are many $k$-cliques that appear to overlap. Does this mean they ...
1
vote
0answers
87 views

Graph algorithms or properties for preserving the topological sort

I got a DAG (directed acyclic graph) on which I can apply a Tsort algorithm (actually its a modified one which also makes sure to visit each node using an ascending node property) in order to ...
5
votes
1answer
162 views

Topological embedding of graph in $\mathbb{R}^3$

I was reading the following proof of the claim that every graph can be embedded in $\mathbb{R}^3$: https://sometimesfun.wordpress.com/2015/08/02/embedding-graphs-in-r3/ At the end, there is the ...
2
votes
1answer
73 views

Embeddings of Complete Graphs and Their Topology

Following standard notations, we use $K_n$ to denote a complete graph with n vertices. We know that $K_1,K_2,K_3,K_4$ are planar graphs and a natural notion of vertex, edge, and face can be visualized ...
1
vote
0answers
37 views

Reference request: Toroidal graph

I have asked a similar question here but not sure if it has reached the right community. I need reference to learn about graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to ...
2
votes
1answer
274 views

topological sort via depth first search: more than one source

If the first node in a Depth First Search is chosen as one of say 2 sources in a directed, acyclic Graph G(V,E), how can a depth-first search ever find the 2nd source since with each iteration it is ...
1
vote
0answers
33 views

Let $G$ be a graph and $\omega$ be its clique number

I have been reading graph theory related to topological indices. I also found a question which is related to topological index (G.A. index) and clique number. Let $G$ be a graph and $\omega$ be the ...
3
votes
1answer
912 views

What is the actual definition of a “Directed Cycle ” in graph theory?

My question is due to a confusion I have in understanding the definition of a DAG. From Wolfram Alpha: "An acyclic digraph [DAG] is a directed graph containing no directed cycles" However I have not ...
0
votes
0answers
88 views

Placement algorithm for chord diagram

What is a good algorithm for placing nodes on a non-ribbon chord diagram so that nodes are likely to be placed near (strongly) connected nodes? A non-ribbon chord diagram is a layout for a graph ...
0
votes
1answer
30 views

$\mathbb{Z^3}$ Simple Cubic Lattice

I'm doing research for my thesis and I'm trying to model some type of DNA-associating proteins. I have not yet picked which I would like to work with, but I figured I should give as much background as ...
5
votes
2answers
2k views

Unique Topological Sort for DAG

I have a DAG (directed acyclic graph) which has more than one valid topological sorting. I'm looking for a way to sort it topologically and always get the same, well defined result. For example take ...
0
votes
1answer
445 views

Torus without a disk

I have troubles to visualize the torus $\mathbb{T}^2$ without a disk $\operatorname{Int}D^2$. I don't see why $\mathbb{T}^2\setminus \operatorname{Int}D^2$ is not the same as $\mathbb{T}^2\#\mathbb{T}^...
1
vote
1answer
53 views

How is the genus of a graph affected by the addition or removal of an edge?

If I add or remove a single edge from a graph, does the genus change by at most a constant amount? More precisely, A graph parameter is a function $f$ that maps graphs to a range $\{1, \cdots, m\}$ ...
1
vote
1answer
96 views

Equivalent arrangements of arrows [closed]

Given $n$ arrows arranged so that every arrow starts from the base of one of the arrows and ends on the base of one of the arrows, what should be meant by that two such arrangements are essentially ...
3
votes
0answers
67 views

Graph map terminology

By a directed multigraph, I mean a tuple $G= (V,E,i,t)$, where $V$ is a set of "vertices," $E$ is a set of "edges," and $i:E\to V$ and $t:E\to V$ are functions giving the "initial" and "terminal" ...
0
votes
1answer
115 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 ...
1
vote
0answers
91 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, ...
2
votes
0answers
58 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 ...
13
votes
3answers
1k views

Mapping The Unit Disc To The Hemisphere?

Question: Can a disc drawn in the Euclidean plane be mapped to the surface of a hemisphere in Euclidean space ? If $U$ is the unit disc drawn in the Euclidean plane is there a map, $\pi$, which ...
1
vote
0answers
36 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 ...
5
votes
2answers
1k 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 ...
3
votes
1answer
1k 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 ...
2
votes
1answer
55 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 ...
4
votes
1answer
758 views

Definition/Clarification of Graph Embeddings

Recently I started reading about graph embeddings, but I am unable to grasp its definition from Wikipedia. Can anyone explain this term with an example.
2
votes
1answer
442 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 ...
4
votes
2answers
369 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 ...
1
vote
1answer
239 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 $+$ ...
0
votes
1answer
281 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 ...
3
votes
0answers
115 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 ...
1
vote
1answer
727 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 ...
0
votes
0answers
72 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 ...
0
votes
1answer
142 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 ...
0
votes
0answers
48 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 ...
0
votes
2answers
491 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 ...
0
votes
0answers
102 views

contraction and minors proof

I want to prove the following proposition $\textbf{proposition}$: $G$ is an $MX$ if and only if $X$ can be obtained from $G$ by a series of edge contractions, i.e if and only if there are graphs $G_{...
0
votes
1answer
365 views

Question regarding normal spanning trees and a proof of existence

I'm reading about normal spanning trees in the Diestel book and i am somewhat confused by a number of things i'll try and work in chronological order. The first thing you need to know is about a tree ...