Questions tagged [planar-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
124 views

Upper bound on the number of triangles in a planar graph

For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller ...
3
votes
1answer
138 views

Partitioning planar graphs without minimizing edge cuts

I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions: Creates balanced (within some margin) $k$ partitions of $V$ ...
3
votes
1answer
747 views

Creating a 2D map of objects given a sparse matrix of pairwise distances

I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for ...
1
vote
0answers
92 views

Is there a fast, "partial planarization" algorithm for non-planar graphs?

On "partial planarization" I understand an algorithm, which tries to reach an optimal, or nearly-optimal solution for non-planar graphs. For example, which minimizes the number of the crossing edges (...
6
votes
2answers
1k views

Algorithm to generate all planar graphs

Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc. ...
6
votes
1answer
1k views

Subgraph isomorphism in planar graphs

I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs. I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-...
1
vote
2answers
612 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...

1
2