Maximum Independent Set in 2-Direction Outersegment Graphs

摘要

An outersegment graph is the intersection graph of line-segments lying inside a disk and having one end-point on the boundary of the disk. We present a polynomial-time algorithm for the problem of computing a maximum independent set in outersegment graphs where every segment is either horizontally or vertically aligned. We assume that a geometric representation of the graph is given as input.