Questions tagged [graph-embeddings]
Use for questions about embeddings of graphs in surfaces of genus greater than 0. For embeddings of graphs in planes, spheres, and other simply-connected spaces, use [planar-graphs].
22
questions
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 ...
0
votes
0
answers
22
views
Embedding a positive-weighted undirected graph in Euclidean space?
Say I have a graph $G$ with $n$ vertices and $m$ undirected positively-weighted edges. I want to embed that graph into $k$-dimensional Euclidean aka Cartesian space such that $k$ is minimal. A valid ...
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 ...
0
votes
1
answer
105
views
Can individual topological space be considered as category?
Of course, I am aware of Top (category of topological spaces). My question is about something different - can any topological space be considered as category? E.g. its objects may be the open sets of ...
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$...
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 ...
1
vote
0
answers
32
views
Find the best embeddding for this gene/lipid graph
I want to find a 'nice' drawing of the lipids and genes in my database. Lipids belong to one one of several classes, while genes belong to one of several regions. Each gene/lipid pair has an ...
0
votes
0
answers
19
views
What are other graphs of order $n$ than the star $K_{1, n-1}$ which are not packable?
We say, that a graph $G$ is packable, if it is isomorphic to a subgraph of its complement.
In more formal terms:
A graph $G$ is packable, if there is a permutation $\sigma : V(G) \to V(G)$ such that
$$...
-1
votes
4
answers
142
views
Prove a mapping is open
Prove that the map $$f:(0,1)\to\mathbb{R}^2$$ $$t\mapsto (\cos 2\pi
t,\sin 2\pi t)$$ is an embedding.
PS: In general topology, an embedding is a homeomorphism onto its image. More explicitly, an ...
4
votes
1
answer
51
views
What is the lowest dimension for topological or isometric embedding of Y^n into euclidean space?
Let $Y$ denote the one-point union of three unit intervals. Since $Y$ embeds isometrically in the plane, it follows that the nth cartesian power $Y^n$ embeds isometrically — and also topologically — ...
0
votes
0
answers
46
views
Counting loops on countable graph embedded on flat torus
I was wondering about the research on countable connected graphs on compact surfaces, in particular the flat torus. In my considerations, I started with the flat torus view by $\mathbb{T}=[0,1]^2/{\...
1
vote
0
answers
59
views
Embedding (possibly approximate) of category into topological space (as a category of open sets of this space)? [closed]
I am thinking about embedding of categories into topological spaces (or even manifolds).
I have found 2 connections:
one can construct the nerve/groupoid from a category and then use homotopy ...
1
vote
0
answers
27
views
Connection between graph realization (embedding) and spectral theory
Definition 1 (realization): Let $k$ be a positive integer and $G = (V, E, d)$ be a simple graph with $n$ vertices, undirected, connected, and with edge weights. Find a function $x: V \rightarrow \...
3
votes
1
answer
48
views
Can we draw the dual graph with straight lines?
I've been investigating this problem:
Given some straight line planar embedding of a simple connected graph with a simple dual graph, does there exist a straight line planar embedding of that dual ...
1
vote
0
answers
22
views
Vertex locations of Dessin w/h Circle packing in Discrete Dessin d'Enfant
I'm reading the following paper.
Bowers, Philip L., and Kenneth Stephenson. Uniformizing Dessins and BelyiMaps via Circle Packing. Vol. 170. No. 805. American Mathematical Soc., 2004.
In the paper, ...