All Questions
Tagged with graph-drawing graph-theory
48 questions
1
vote
1
answer
98
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 1,190
1
vote
1
answer
115
views
Bounds on lengths of boxes in bounded-degree box graphs
$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\cub}{\operatorname{cub}}$
This is a follow up and an extension of another question I asked recently.
A box graph is a graph ...
- 277
1
vote
1
answer
194
views
Bounds on lengths of intervals in bounded-degree interval graphs
A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the ...
- 277
2
votes
0
answers
73
views
Is the chromatic number of every 7-connected 1-planar graph at most 5?
1-planar graphs were first studied by Ringel (1965), who showed that they can be colored with at most seven colors. Later, the precise number of colors needed to color these graphs, in the worst case, ...
- 1,851
1
vote
0
answers
42
views
What lower bounds are known for pair crossing number and related questions in multigraphs?
So in terms of crossing number https://arxiv.org/pdf/1808.10480 gives a lower bound of $O(e^{2.5}/n^{1.5})$ for multigraphs with no face of length 2 with no node contained inside.
What do we know ...
- 111
1
vote
0
answers
97
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 ...
- 111
1
vote
0
answers
77
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges.
Call the set of ...
- 111
5
votes
0
answers
198
views
"separators" for nonplanar graphs embedded in the plane
Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small ($o(|V(G)|$) subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an ...
- 111
2
votes
0
answers
63
views
What is the range of connectivity for maximal IC-planar graphs?
A graph is IC-planar if it admits a drawing in the plane with
at most one crossing per edge and such that two pairs of crossing edges
share no common end vertex. A graph $G$ is maximal in a graph ...
- 1,851
1
vote
1
answer
173
views
Who introduced the concept of beyond planar graphs?
The concept of planar graphs seems to be standard (I'm also not sure who first used this term), and recently, beyond planar graphs attract a lot of interest in the field of graph drawing. I know that ...
- 1,851
0
votes
0
answers
81
views
Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?
A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.
A minor of graph G is a graph obtained from G by ...
- 1,190
6
votes
3
answers
526
views
Enumerating all inequivalent planar embeddings of a planar graph
Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
- 1,851
3
votes
0
answers
136
views
Is there a more intuitive proof that a 1-planar graph with minimum degree 7 contains a $K_4$?
In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1.
Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." ...
- 1,851
20
votes
3
answers
1k
views
Can a 3-regular non-1-planar graph be constructed?
A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.
I used nauty to generate all 3-regular graphs up to ...
- 1,851
7
votes
0
answers
155
views
Why is the crossing number of Tutte 12-cage 170?
From the Wikipedia entry on Tutte 12-cage , it is stated that the crossing number of Tutte 12-cage is 170, but the cited references do not seem to provide sufficient explanation for this.
Exoo, G. &...
- 1,851
1
vote
0
answers
66
views
A confusion about the proof of maximal 1-plane graph being $2$-connected
It is well known that every maximal planar graph with at least 4 vertices is 3-connected. But for maximal 1-planar graphs we cannot ensure the high connectivity. (See is-there-any-maximal-1-planar-or-...
- 1,851
6
votes
1
answer
712
views
How to construct a 5-regular 1-planar bipartite graph?
A graph is 1-planar if it can be drawn on the plane such that each edge is
crossed at most once.
Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed ...
- 1,851
1
vote
0
answers
141
views
Does contracting a non-crossing edge of a $k$-plane graph change the $k$-planarity?
A graph is $k$-planar if it can be drawn on the plane such that each edge is
crossed at most $k$ times. A graph together with a $k$-planar drawing is a $k$-plane
graph. Hence, by definition, $0$-...
- 1,851
4
votes
1
answer
214
views
Find all 2-planar drawings of $K_6$ and $K_7$
A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per
edge.
It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$.
Angelini P., Bekos M. A., ...
- 1,851
9
votes
3
answers
470
views
Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?
A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...
- 557
5
votes
1
answer
220
views
Is the crossing number of the line graph of $K_5$ determined?
The line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$. $L(G)$ is constructed in the following way: for each edge in $G$, make a vertex ...
- 1,851
8
votes
1
answer
527
views
Find all Non-isomorphic good drawings of $K_{3,3}$？
Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere.
Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with ...
- 1,851
3
votes
1
answer
156
views
Constructing a 1-planar graph that has no rectilinear drawing
A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge.
1 planar graph
I read the ...
- 1,851
1
vote
1
answer
160
views
Can Tutte embedding be guaranteed that each face is convex?
In graph drawing and geometric graph theory, a Tutte embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a ...
- 1,851
1
vote
1
answer
293
views
Abnormal toroidal drawing of graph
1. Some background knowledge
Definition. A torus, informally, is the doughnut-shaped surface that we get by taking a square made out of some arbitrarily-stretchy material and gluing together opposite ...
- 1,851
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
4
votes
0
answers
131
views
What is the crossing number of dodecahedron with a copy of $K_5$ inside each face
Suppose we are given a regular dodecahedron. Then we add five crossed edges inside each of its faces (actually, inside each face it is a copy of $K_5$). It is clear that this drawing has 60 crossings. ...
- 1,190
5
votes
1
answer
263
views
What is the crossing number of cube with a pair of crossing edges inside each face
Suppose we are given a cube and we add a pair of crossing edges inside each of its faces. It is clear that this drawing has 6 crossings. My question is whether such a graph has crossing number 6? How ...
- 1,190
5
votes
2
answers
251
views
Finding a special plane graph with some requirements on the faces
Is there a plane graph such that
(1) the outer face has degree 3, i.e, is a triangle,
(2) every inner face has degree 5, and
(3) any two degree 5 faces share at most one commong edge.
- 1,190
3
votes
1
answer
200
views
Looking for examples showing that the crossing number may not be realized by the drawings with local crossing number
The crossing number $cr(G)$ of a graph $G$ is the lowest number of edge crossings of a plane drawing of the graph $G$. The local crossing number of a drawing of a graph is the largest number of ...
- 1,190
7
votes
2
answers
252
views
There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?
Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?
- 1,190
6
votes
2
answers
293
views
Is there any maximal 1-planar or 2-planar graph that is not 3-connected
A graph is $k$-planar if it can be drawn in the plane so that each edge is crossed at most $k$ times. A $k$-planar graph $G$ is maximal if $G+uv$ is not $k$-planar for any non-adjacent vertices $u,v\...
- 1,190
1
vote
1
answer
75
views
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of "curves"?
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ ...
- 111
10
votes
2
answers
599
views
Method to draw 3-connected planar graph on a sphere
The Tutte embedding is a way to create a "nice" drawing of a 3-connected planar graph in the plane, after having chosen an outer face.
Is there a similar method to draw such a graph on a sphere? ...
- 911
5
votes
2
answers
553
views
"Locally Nonplanar" graph
A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and ...
- 1,034
7
votes
0
answers
87
views
Universal point sets for 1-plane graphs
It is a notorious open problem to find a smallest set of $N$ points that
permit any $n$-vertex planar graph to be drawn in the plane without
crossings, using only those $N$ points as vertices, and ...
- 151k
3
votes
2
answers
123
views
Number Associated with Straight-line Drawings of Hamiltonian Graphs
Is there anything known about the maximum number of simple-polygonal Hamilton cycles that a straight-line drawing of a Hamiltonian graph can have?
Put differently, if the vertices of a Hamilton ...
- 13.2k
5
votes
2
answers
474
views
Another graph characteristic
This question concerns a method of drawing graphs and a graph characteristic about which I want to learn more.
Consider a connected directed graph with at least one node with in-degree 0 and one node ...
- 9,720
5
votes
1
answer
479
views
Can all crossings in a graph be moved to one point?
Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all ...
- 4,829
5
votes
0
answers
230
views
Minimal algebraic degree of symmetric unit distance embedding of Heawood graph
I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates ...
- 10.7k
4
votes
1
answer
393
views
Example to show pairwise crossing number is not equal to crossing number
A common point of two edges in a graph drawing that is not an incident vertex is called a crossing.
The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of $G$....
user39815
12
votes
3
answers
1k
views
Is every graph an edge-crossing graph?
Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
- 195
10
votes
2
answers
724
views
Bounds on chromatic number of $k$-planar graphs
A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...
- 151k
1
vote
1
answer
228
views
Counting edges in embeddable CW-complexes in R^3
Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...
- 415
13
votes
1
answer
933
views
Drawings of complete graphs with $Z(n)$ crossings
Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
- 6,101
8
votes
7
answers
2k
views
Visualizing polyhedra from their 1-skeletons
Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton embedded in the plane, e.g. the hexahedral graph 5, as can be seen here.
...
- 9,720
2
votes
0
answers
246
views
A primal-dual (double) circle packing (coin graph) question
I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem).
Q1- But I am not sure whether ...
- 415
7
votes
2
answers
1k
views
Planar layouts of bipartite graphs
Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.
It would be very convenient if there was a ...
- 4,462