790
edits
Changes
Jump to navigation
Jump to search
Line 23:
Line 23: + + + + + + + + +
→Planarity algorithm
===Planarity algorithm===
===Planarity algorithm===
The planarity algorithm is used to determine whether a given shape is 2-dimensional or not. It has found particular use in road and circuit board design to avoid cross-overs.
#Identify a [[Hamiltonian Cycle]] in the network.
#Redraw the network with the Hamiltonian cycle on the outside.
#Identify any crossings between lines.
#Choose an arc with crossings to stay inside the cycle. Move any arcs with crossings to the outside.
#Repeat from step 3 until there are no more crossings. If this step is completed, it shows that the shape is planar (2-d). If it cannot be completed, the shape is 3-dimensional and not planar.
===Critical path analysis===
===Critical path analysis===
===Kruskal's algorithm===
===Kruskal's algorithm===