nvcleemp/planarity

Automatically exported from code.google.com/p/planarity

planarity's Issues

Vertex coloring method should receive extra parameter to allow control of degree 5 neighborhood contraction

The vertex coloring method uses minimal degree selection for reducing the 
graph.  This alone guarantees a maximum of 6 colors of any graph that 
happens to be planar.
The method also uses the concept of contracting the neighborhood of degree 
5 vertices that are reduced, guaranteeing a maximum of 5 colors on any 
planar graph.
When Matula, Shiloach and Tarjan introduced the neighborhood contraction, 
they proved that there would be at least one degree 5 vertex in a planar 
graph that had a pair of non-adjacent neighbors both of degree 11 or 
less.  This guaranteed linear time performance for the 5-coloring.
Later, Frederickson proved that there would be a degree 5 vertex in any 
planar graph whose pair of non-adjacent neighbors would each be degree 7 
or lower.
The current implementation uses the degree bound of 7, the idea being that 
the lower degree bound would mean spending less time contracting a 
neighborhood.

Enhancements:
1) But if one does not need planar graphs to be 5-colored, e.g. if one 
just needs a decent coloring, then it would be nice to shut off the 
neighborhood contraction altogether since it does produce a reasonable 
percentage increase of performance.  
2) Also, it would be nice to also use the degree bound first suggested by 
Matula, Shiloach and Tarjan.  This would mean potentially more time 
contracting neighborhoods, but also possibly more graphs would be colored 
with fewer colors while still achieving O(n) performance.  It would fun to 
experiment with this alternative.

Original issue reported on code.google.com by [email protected] on 25 Feb 2010 at 3:10

In K3,3 search, restore reduced paths should delete first then insert

What steps will reproduce the problem?
1. In nauty/outproc.c change edge capacity to less than will accommodate a 
complete graph.  To guarantee reproduction of problem, use half the number 
edge records needed
2. Run debug version, planarity -nauty -3 11

What is the expected output? What do you see instead?

Failure will happen just short of 40 million graph mark (about 30 minutes) 
from function _RestoreAndOrientReducedPaths() in graphK33Search.c.  The 
function _RestoreReducedPath() as the same problem.

The issue is that a path is reduced by putting an edge in to represent it, 
and restoring the original path is being done by first adding the two 
edges that reconnect the path into the graph, then deleting the edge 
representing the reduced path.  Sometimes, the second of the two edge 
additions fails due to the edge capacity restriction.

The more proper implementation is to first delete the path reduction edge, 
then insert the two edges that reconnect the path into the graph.

Since the number of edges is one greater than desired for a very short 
time locally within the functions, one may accommodate for this problem by 
simply ensuring the graph allows one more edge (two more records) than is 
needed.  For example, K3,3 search is guaranteed to succeed on 3n edges, so 
one could simply allocate 3n+1 edges.  However, it is preferrable to not 
encumber the graph library user with this detail.

Please use labels and text to provide additional information.

Original issue reported on code.google.com by [email protected] on 5 Apr 2009 at 6:34

The function gp_EnsureEdgeCapacity is misnamed

The caller of the function gp_EnsureEdgeCapacity() is quite tempted to 
pass a maximum number of edges desired, not a maximum number of edge 
records. Two edge records are needed per edge to represent it in both of 
its vertex endpoints.

Either rename to gp_EnsureArcCapacity() or have the function internally 
multiply by 2.  Internally, the edgeCapacity member of a graph structure 
will likely become arcCapacity.  In this case, if the public functions 
keep the name 'EdgeCapacity', then ensure that gp_GetEdgeCapacity() 
divides by 2 for consistency with the parameter to gp_EnsureEdgeCapacity().

Original issue reported on code.google.com by [email protected] on 5 Apr 2009 at 6:39

The embedded directory for RandomGraphs() should get adj list graphs

When the random graph generator runs, the user has the option of storing 
embedded graphs in the /embedded directory and adj list representations of 
the embeddings in the /adjlist directory.

The embedded directory receives adj matrix format files. Adj matrix 
doesn't preserve the embedding, so the files being stored are embeddable, 
but they are not embedded graphs.

The graphs stored in adjlist belong in the embedded directory, and then 
there should be a chance to store the matrix format of embedded files in 
a /matrix subdirectory.

Original issue reported on code.google.com by [email protected] on 1 Feb 2010 at 12:38

Optimize Preprocessing through Consolidated DFS and Lowpoint

Creating the DFS tree is currently a separate operation from calculating 
the least ancestor and lowpoint values for vertices.

The least ancestor and lowpoint values can be calculated while also 
creating the DFS tree, which would optimize preprocessing needed by all of 
the planarity-related algorithms

Original issue reported on code.google.com by [email protected] on 29 May 2010 at 6:57

Problems bulding under OSX llvm-gcc

(see:  https://github.com/hagberg/planarity/issues/1)

Seeing various errors, including duplicate symbols errors.

Notably:  "Mode" and friends from `planarity.h`

I realize the build system under that project is very different than in your 
`.cproject` file, but if you have any ideas, they would be welcome!

Original issue reported on code.google.com by [email protected] on 7 Aug 2014 at 4:25

Integrity test for planar graph drawing should accommodate disconnected graphs

Algorithmically interesting part of drawing method occurs on biconnected 
input, but the implementation handles cut vertices and even disconnected 
graphs implicitly.  However, it's a little more work to *test* integrity 
of drawings in the disconnected case, so testing has been confined to all 
connected graphs.
Fix it so that integrity test extends to disconnected case since we're now 
enhancing to that level across all methods.

Original issue reported on code.google.com by [email protected] on 5 Apr 2009 at 10:20

Expose the capabilities of RandomGraph() to command-line

The RandomGraph() method generates a maximal planar graph or a maximal 
planar graph plus a given number of extra edges.  It is now capable of 
running all the extension algorithms, not just the core planar embedding 
algorithm.

The menu-driven interface exposes this capability. 

The command-line version should accept an additional parameter to indicate 
what command should be run in the -rm and -rn cases.

Original issue reported on code.google.com by [email protected] on 1 Feb 2010 at 12:47

Controlling the number of extra edges for RandomGraph()

The RandomGraph() function allows a number of extra edges to be added once 
a random maximal planar graph is generated.
The menu (reconfigure to mode n) and command line (the -rn setting) should 
be enhanced to allow control of the number of extra edges added.  
Currently, the above cases are set to one extra edge only.

Original issue reported on code.google.com by [email protected] on 1 Feb 2010 at 12:49