The planarity algorithm and Hamiltonian cycles Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
13 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 13 cards
- Define a Hamiltonian cycle.
- A cycle that passes through every vertex once and only once and returns to its start vertex.
- How many edges does a Hamiltonian cycle of a graph with vertices have?
- Eulerian cycle versus Hamiltonian cycle?
- Eulerian: every edge exactly once. Hamiltonian: every vertex exactly once.
- Can a tree have a Hamiltonian cycle?
- No: a tree has no cycles.
- What is a planar graph?
- A graph that can be drawn with no edges crossing.
- Which graphs does the planarity algorithm start from?
- A graph with a Hamiltonian cycle, drawn as a closed loop.
- What is a chord in the planarity algorithm?
- An edge of the graph that is not in the Hamiltonian cycle.
- When do two chords conflict?
- When their end points alternate around the cycle, so they cannot both be on the same side.
- Do chords that share a vertex conflict?
- No.
- Where must two conflicting chords be drawn?
- On opposite sides of the cycle: one inside, one outside.
- When does the planarity algorithm show a graph is non-planar?
- When a chord conflicts with chords on both sides, so it has nowhere to go.
- Is planar? Is planar?
- is planar. is not planar.
- What is a route that visits every vertex once but does not return to the start?
- A Hamiltonian path, not a Hamiltonian cycle.