Mathematics Stack Exchange
Mathematics Stack Exchange

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.

In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs.

Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three-cottage problem. More important applications can be found in printing electronic circuits where the aim is to print (embed) a circuit (the graph) on a circuit board (the surface) without two connections crossing each other and resulting in a short circuit.

106 questions
3
votes
1 answer

planar graphs with minimum degree 4

Is it true: there is a simple planar graph $G$ with minimum degree $4$, each $2$ vertices of degree $4$ are nonadjacent $G$ has no vertices of degree $5$.
Engelssina Tasseva
  • 33
1
vote
0 answers

Maximum minimum degree of a graph embedded on a surface

We shall consider only simple graphs. Let $G$ be a graph 2-cell embedded in a surface having Euler characteristic $\chi$. Let $\delta(G)$ be the minimum degree of $G$. Define $\delta_{\chi} = max \{\delta (G)$ : a graph $G$ is 2-cell…
Vlado Dimitrov
  • 11
1
vote
0 answers

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.
Tony Phillips
  • 11
0
votes
1 answer

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
Michele Impedovo
  • 9
0
votes
1 answer

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 if we add a cycle $u_1-u_2-\ldots-u_d-u_1$ to $G$…
Cyriac Antony
  • 552
0
votes
1 answer

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 torus of genus $2$ to embed ... Is there a formula…
J. Schmidt
  • 333
  • 1
  • 9
0
votes
1 answer

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 are overlapping communities?
Joey Carson
  • 103
0
votes
1 answer

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 the surface normals of each triangle. Now, I want…
Brandon
  • 465
  • 4
  • 15