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.

Filter by
Sorted by
Tagged with
0
votes
0answers
32 views

Chromatic Number of $S_2$

What is the largest chromatic number of all the graphs $G$ that can be embedded on $S_2$ (the double torus)? To which graph is it associated?
0
votes
1answer
32 views

What is the chromatic number of S2?

How can one find the chromatic number of the orientable surface S2 (the double-torus)? Does anyone know of an example which shows this chromatic number by giving an upper bound and a lower bound? ...
0
votes
0answers
38 views

Beauty of Spectral Graph Theory

Why would one choose to study spectral graph theory? Where can the spectrum of complete graphs, for example, be applied in real- life example or of any graph in general? A brief historical background ...
1
vote
2answers
51 views

Purpose of imbedding a group onto a surface?

I'm reading the book "Topological Graph Theory" by Gross and I've gone through a fair bit of it. It seems like the entire book is leading up to being able to imbed a group onto a surface, and I have ...
0
votes
2answers
22 views

Cycles in Plane Graphs

For a plane graph $G$, if $C$ is a cycle in $G$, can $G$ be embedded in the plane so that $C$ is the face boundary of the outer face of $G$?
1
vote
1answer
27 views

Counting Topological Sorts Of Graph With In Degree 1

I was asked this question recently and am struggling to come up with the closed form solution: How many topological sorts are there for a directed acyclic graph where each vertex only has one incoming ...
2
votes
2answers
49 views

Isomorphisms of Planar Embeddings

My question: How does one distinguish between two embeddings of the same graph on the plane? For instance, are two such embeddings considered the same if the degree sequence of their faces are the ...
1
vote
1answer
52 views

Isomorphisms of Graph Embeddings

I am having trouble understanding isomorphisms of graph embeddings. How does one distinguish between two graph embeddings on the same surface, and how does one, for example, distinguish between two ...
0
votes
1answer
28 views

Are all topological graphs geometric graphs?

A topological graph or string graph is an intersection graph of curves. Can all such curves be drawn as intersection graph of line segments?
3
votes
1answer
52 views

An extension of the Utilities Problem. (for $n$ utilities) I want to find sufficient conditions to make it work.

We know that the Utility Problem asks to connect three utilities to three houses without crossing utilities line. I can prove that there is no solution in the plane or $S^2$, but it is solvable on ...
-1
votes
1answer
32 views

Equal degree sum of two graph shows they have equal vertex degrees??

I am looking for the answer of the question if two graphs have equal degree sum, then whether both have equal vertex degree.i.e., If $G$ has vertices $d_{i}$ and $G^{\prime}$ has vertices $d^{\prime}_{...
0
votes
0answers
60 views

Is a topological graph intiutively embedded in a Hausdorff space?

I'm having trouble understanding topological graph theory. Given an abstract graph $G=(V,E)$, then $G'$ is an embedding of $G$ in a topological space $X$, if each edge of $E$ is represented by an arc ...
1
vote
0answers
41 views

(path)Connectedness of a simplicial complex Vs it's $1$-skeleton

Let $\Delta$ be an abstract simplicial complex https://en.m.wikipedia.org/wiki/Abstract_simplicial_complex and $|\Delta|$ be its geometric realization. Let $\Delta ^{(1)} :=\{F $ is a face of $\...
1
vote
0answers
29 views

genus of regular bipartite graph

Is there a formula for the genus of a bipartite graph with 2 sets of m vertices, where each vertex has order 3? I.e. if m=3 this is K(3,3). But I'm interested in larger m.
0
votes
2answers
87 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
41 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
98 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
1answer
236 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
110 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
37 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
124 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 ...
7
votes
1answer
210 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
77 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
70 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
39 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
134 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
22 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
131 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
282 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
119 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
47 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
371 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
38 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
2k 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
101 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
32 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
3k 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
637 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
62 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
100 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
128 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
117 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
2k 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
37 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
2k 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
2k 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
71 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 ...