Skip to content
No description, website, or topics provided.
C++
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
graphs
proofs
NOTES
README
circ_list.cpp
circ_list.h
main.cpp
main_helper.cpp
makefile
node.cpp
node.h
vertex.cpp
vertex.h

README

This is a coding project by Josh Mermelstein and Michael James in the summer of 2012 for the
Tufts CS departament.  Its goal is to create a program that can take a
non-planar graph and determine if there is a way to make it planar by copying
any number of vertices while preserving connections.

The overall structure is centered on a circular doublely linked list which is
specified in the circ_list files.

the following is the format in which the program reads in a graph:
the first line will be the number of vertices
every subsequent line will represtent a new vertex whose index is the line
number -1
Each of these lines will end in a newline character.
The program internally runs from 0->n-1 but all inputs and outputs should be from 1->n.

some known information.

Planar Expandable graphs
K_6
K_{3,4}
K_{2,2,3}
K_{3,3,1}
K_{4,2,1}
K_7 with 4 edges missing (all 4 sharing a vertex)
	(make a drawing of a K_6 and put a new vertex inside of a triangle)
K_7 with 4 edges missing (no vertex missing more than 2)
	(example of missing edge set, 12, 34, 35, 56
	make a K_2211 and put the final vertex in the square)


Proven non-planar expandable
K_7
K_{4,4}
K_{3,5}

Suspected expandable


suspected non expandable
any two planar expandible graphs connected by one edge
a K_7 with two edges missing (not sharing a vertex)
a K_7 with two edges missing (sharing a vertex)

Running theories
Eli:
	40% undecidable, 55% linear time solvable, 5% more than linear time
Ben:
	Maybe decidable but worth considering that it is undecidable.
	If it is decidable, then no vertex needs to be used more than twice
Michael:
	It could be anywhere from undecidable to NP-complete.
Josh:
	Probably decidable
	If one can partition the verticies into two sets such that each set is
	non-planar (even if that set is planar expandable) then the graph is not
	planarexpanable. (also the graph is connected)
You can’t perform that action at this time.