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.

76 questions
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 ...
32 views

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"?
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 ...
30 views

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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...