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
2
votes
1answer
40 views

Automorphisms of directed surface graphs

I came across a problem where I need to be able to find automorphisms of a directed graph embedded on a surface. WLOG, I can assume the surface is a plane (if that is helpful). Normally, a graph ...
4
votes
0answers
40 views

What is Euler's Formula when 2­-cell embedding condition was removed?

It is well known that Euler's Formula for genus $\gamma$: For every 2­-cell embedding of a graph on a surface with genus $\gamma$, the numbers of vertices, edges, and faces satisfy $n-e+f=2-2\gamma$. ...
4
votes
1answer
73 views

Construct the smallest graph homeomorphic to a given graph by smoothing

The homeomorphism class $ \mathcal{H}(G) $ of a graph $G$ is the set of isomorphism classes of graphs that are topologically homeomorphic to $G$. It is natural to ask: Is there a "smallest" ...
2
votes
1answer
82 views

Bijective projection from a unit disk to a unit sphere

Is there any proper method that makes conformal one-to-one mapping (preserving the angles) from a unit disk to a unit sphere? I know with simple stereographic projection you can project a unit disk to ...
5
votes
0answers
80 views

Chromatic Number Range of Dual Graphs?

A planar graph $G$ has some set of embeddings $\{E_\gamma:G \hookrightarrow R^2\}$. Each of these embeddings has associated with it a geometric dual graph $G^*_\gamma$. Using $\chi$ to denote ...
0
votes
0answers
37 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
49 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
1answer
86 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
56 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 ...
1
vote
2answers
73 views

For any cycle, must there exist a planar graph embedding with it as the face boundary?

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
101 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
124 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
114 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
35 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
86 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
40 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}_{...
1
vote
0answers
98 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
34 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
138 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
52 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
111 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
335 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
127 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
55 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
180 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 ...
9
votes
2answers
370 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
90 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
86 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
40 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
166 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
154 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
367 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
177 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
1answer
67 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
432 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
41 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
106 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
34 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
4k 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 ...
1
vote
1answer
905 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
74 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
103 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
69 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
138 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
130 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
62 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 ...