All Questions
Tagged with planar-graphs discrete-geometry
7 questions
10
votes
2
answers
441
views
Graph planarization via rewiring
Let $G$ be a nonplanar graph (undirected) of $n$ nodes and $e$ edges, with
$e \le 3n-6$.
Define a rewiring move as replacing edge $(a,b)$ with edge $(a,c)$.
The result must be a simple graph (no loops,...
- 151k
3
votes
0
answers
222
views
Reconstructing plane graphs from degree- and face-sequences
Let $G$ be a plane $3$-connected graph; so it partitions the plane
into regions bounded by faces.
Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$,
and $\mathrm{deg}_f$ be the sequence of ...
- 151k
2
votes
1
answer
95
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 ...
- 111
1
vote
1
answer
114
views
Removing a face from 4-connected planar graph
After removing a face (vertices along with edges) of a 4-connected planar graph, is the remaining graph 4-connected? Alternatively under what conditions is this true?
- 129
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
1
vote
0
answers
149
views
Determine sub-polygon from line segments with known member connectivity
Test Polygon:
Consider the following polygon as attached. Let the known parameter be as follows:
•Member to member connectivity, i.e. it is known that A – B, X – E, F – B, etc. for all the members.
•...
- 19