All Questions
Tagged with planar-graphs algorithms
33
questions
1
vote
0
answers
33
views
Degree of the neigbour verticies of a vertex degree 5 in a planar graph - visualization
I'm writing a lecture on 5-coloring planar graphs and I'm having trouble visualizing this inequality form the proof
"$2n_5 \leq \sum_{d \geq 12} dn_d$"
I want to make a simple drawing of ...
0
votes
1
answer
73
views
Irrigation problem as a graph coloring problem
I am trying to solve an interesting problem in graph coloring which I believe is related to the vertex cover problem.
The graph is a $12 \times 12$ grid, representing a field. The field needs to be ...
- 137
0
votes
0
answers
14
views
Find sequence of point from $u$ to $v$ such that each is at distance $d(u,v) = t$ with $t \in [1,2]$.
The problem is the following:
Given $n$ points in $\mathbb{R^2}$, give an algorithm that given points $u$ and $v$, $u \neq v$ find a sequence of points such you can go from $u$ to $v$ and in each step ...
4
votes
1
answer
310
views
Fast algorithm to embed a triangulation into plane
Let $G = (V, E)$ be a planar graph such that $|E| = 3|V| - 6$ (so $G$ must be a triangulation without Kuratowski subgraphs). Given the adjacent matrix $A$ of $G$, please design an algorithm to embed $...
- 1,008
2
votes
1
answer
148
views
Reaching the grid graph from a planar graph using graph transformations
Consider a $5$-regular undirected planar graph with $n$ vertices (a $k$-regular graph has exactly $k$ edges emanating from every node.)
Let us say we apply an arbitrary sequence (of length $\text{poly}...
- 135
0
votes
0
answers
45
views
Proposition of fast algorithm for graph with weights
If ever your Djkstra algorithms are in a situation where the max weight is much smaller than the number of vertices in your graph, try transforming each weight of size "x" into "x" ...
2
votes
0
answers
852
views
Find all minimal cycles (Graph Theory)
I am facing the following problem, let $G(V, E)$ be an unweighted planar graph, find all the minimal cycles of $G$.
[UPDATE 1] A minimal cycle $c$ of $G$ is a cycle in $G$ such that there is no edge ...
1
vote
0
answers
108
views
Generate a new planar graph via edge subdivision and edge addition
Given a simple planar graph $G$, let $G'$ be a subdivision of $G$. Examples of $G$ and $G'$ are shown below:
The graph $G'$ is clearly planar. Let $W = \{w_{i,j} : (v_i, v_j) \in E(G)\}$ be the set ...
- 250
2
votes
1
answer
272
views
Is there an algorithm for constructing a Triangle Hierarchy for maximal planar graphs?
In the research I am currently involved in, I am given a planar, maximal graph $G$ of $n$ vertices, and its embedding. I require to find a structure, which I call a "triangle hierarchy" of $...
- 79
1
vote
0
answers
50
views
Uniform sampling $k$ non-crossing $s$-$t$-paths in plane graph.
Let $G=(V, E)$ be a graph embedded in the plane and let $s, t\in V$
both lie on a common face. Shortest non-crossing $s$-$t$-paths $P$
and $P'$ are shortest paths (wrt. edge count) from $s$ to $t$ ...
- 961
3
votes
0
answers
77
views
counting cycles and paths in simple graphs
I'm newly studying graphs in my school courses and I've been facing this common type of questions about how many cycles/paths are there between some vertices I asked my teacher for a simpler or more ...
- 176
2
votes
1
answer
185
views
Algorithm for checking if a given embedding is planar in less than $O(n^2)$ time.
Given an embedding of a graph (with that I mean a concrete spacial layout of the graph on the 2D plane with only $n$ straight edges. Is this the right terminology?), how can I determine if that ...
- 135
4
votes
1
answer
259
views
Two from Cubic Subgraph Hardness
The Problem
For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3.
The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
2
votes
1
answer
130
views
Map colouring algorithm for rectangular regions
We are interested in the class of maps formed of rectangular regions drawn on squared paper (or blocks of cells on a spreadsheet). So the adjacency graph has a natural ordering from the top-left to ...
- 3,017
0
votes
1
answer
182
views
Graphs: Recognizing a $P_4$ subgraph
I'm trying to build an algorithm that says if a graph is trivially perfect or not. I realized that I can look if a graph is $(C_4, P_4)$-free as they are equivalent. (https://graphclasses.org/classes/...
