Special Issue on Selected Papers from the Fourteenth International Symposium on Graph Drawing, GD 2006
Upright-Quad Drawing of st-Planar Learning Spaces
Vol. 12, no. 1, pp. 51-72, 2008. Regular paper.
Abstract We consider graph drawing algorithms for learning spaces, a type of st-oriented partial cube derived from an antimatroid and used to model states of knowledge of students. We show how to draw any st-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an st-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant. Our results imply that an antimatroid has order dimension two if and only if it has convex dimension two.
Submitted: December 2006.
Revised: February 2008.
Communicated by Michael Kaufmann and Dorothea Wagner
article (PDF)