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.
111
questions
1
vote
0
answers
22
views
Number of distinct minimal fundamental cycle matrix of rank $k$
For a graph $G=(E,V)$ and a fundamental cycle basis $C_1,\ldots,C_k$, we can create a incident matrix $M$ between the edges and the fundamental cycles. Namely, $M_{i,j}=1$ if $e_i\in C_j$, and $M_{i,j}...
- 5,848
0
votes
0
answers
16
views
Dipping into sets of parallel edges in graph drawings
Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell ...
- 468
3
votes
1
answer
290
views
Problem related to crossing number
Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$.
Denote $\delta(v)$ the set of edges with one ...
- 468
3
votes
2
answers
322
views
Is it true if a face of a graph is not homeomorphic to an open disk, then we may find a noncontractible curve contained in the face?
Suppose we have a graph embedded on a surface $Q$ and one face $F$ of the graph is not homeomorphic to an open disk. Does there exist a closed (smooth nonselfinteresecting) curve $g$ contained in $F$...
- 468
2
votes
1
answer
42
views
Genus of a graph consisting of two faces homeomorphic to open disks
Suppose the graph $G$ is embedded in a surface $Q$ such that there are two faces $F_1,F_2$ of the embedding, each homeomorphic to the open disk, such that each node of $G$ lies on $F_1$ or $F_2$.
Is ...
- 468
1
vote
0
answers
33
views
Assessing the homogeneity of a dendrogram
I'm developing a model that organises items of different classes into a dendrogram, like the one here:
A dendrogram showing items of 6 different classes
I'm wondering how I can assess the homogeneity (...
1
vote
1
answer
43
views
Vietoris-Rips complex with repeated vertices
I am trying to study Vietoris-Rips complexes that arise from a point data sample, in the context of topological data analysis. Each data point maps to a point in a metric space by some measurement ...
- 65
1
vote
0
answers
59
views
The only irreducible triangulation of $S^2$
I have been reading "An Introduction to Computational Topology" by Herbert Edelsbrunner and John Harer and they give the following exercise question in the second chapter of the book on &...
- 11
1
vote
0
answers
24
views
Clique complex of expander graphs simply connected?
Given an expander graph family (an injective sequence of graphs with uniformly bounded vertex degree and a Cheeger constant/Laplacian spectral gap uniformly bounded away from zero).
Can the ...
1
vote
1
answer
119
views
Special Book Embeddings
I am taking a course on Topological Graph Theory, where we have looked into the topic of Book Embeddings. The particularly interesting ones were Book Embeddings with thickness 2. This essentially ...
- 127
1
vote
0
answers
34
views
Structural characterizations of planar graphs
I'm looking for as many characterizations of planar graphs, preferably those that are more `structural'. Wagner's and Kuratowski's results get close, but the characterizations of Whitney and Maclane ...
1
vote
1
answer
82
views
Binary optimization on a direct-acyclic-graph(DAG)
Given a DAG $G$, each edge of the DAG $e \in E(G)$ relates to a attribute $w_e \in \{-1, 1\}$
Try to find the optimized attribute setting $[w_e]$ s.t. the cost function
$$
\sum_{e\in E(G)} w_e
$$
is ...
- 11
0
votes
1
answer
50
views
Analyse the dimension by putting a graph into euclidean space without edge intersection
Say we have a graph which has maximum $k$-clique as its subgraph. Let us try to put each vertices of the graph into Euclidean space without having any intersection of edges. Note that we assume that ...
- 341
1
vote
0
answers
75
views
almost planar graphs are minor closed
I'm trying to show that almost planar graphs are minor-closed. For that I need to show if $G-e$ is planar, then $G/e$ is almost planar (and vice versa).
My approach: I'm trying to show this using the ...
- 831
2
votes
1
answer
59
views
What's wrong with my map of the hemicube?
Reading from The Foundations of Topological Graph Theory by Bonnington and Little, a map is defined as a set $X$ with two permutations $\pi$ and $\varphi$ such that the orbits of $\pi$ are all of size ...
- 2,258