Abstract

Title: Δk-Confluent and Ok-confluent Graphs
Published: June 2007
Authors: Michael J. Pelsmajer, Marcus Schaefer, Kevin Stern
Abstract: In this paper we extend the concept of Δ-confluence to Δk-confluence by allowing more generalized junctions, called Δk-junctions. We present an algorithm for recognizing graphs that are Δk-confluent. We then generalize Δk-confluence to Ok-confluence by allowing non-intersecting chords within a junction, resulting in Ok-junctions. We present an algorithm for recognizing graphs that are Ok-confluent. Finally, we show that the clique problem can be solved in polynomial time for Δk-confluent graphs.
Full Paper: [postscript, pdf]