Graph-theoretical properties of parallelism in the digital plane Original Research Article

We propose different graph-theoretical algorithms to partition a set of digitized lines into parallel groups, i.e., subsets in which each line is parallel to the other lines in the subset. The slope of a digitized line is not a fixed real number, but is represented by an interval. Likewise, the parallel relations of a collection of lines are represented by an interval graph. The extraction of parallel groups is then equivalent to the detection of cliques in the interval graph. We also consider other partitioning methods, for example, methods based on minimum dominating sets, and on simplicial elimination orderings. In addition, we compute the number of ways in which we can divide a set into parallel groups.