Grid drawings of k-colourable graphs

Research output: Contribution to journalArticleResearchpeer-review

13 Citations (Scopus)

Abstract

It is proved that every k-colourable graph on n vertices has a grid drawing with O(kn) area, and that this bound is best possible. This result can be viewed as a generalisation of the no-three-in-line problem. A further area bound is established that includes the aspect ratio as a parameter.
Original languageEnglish
Pages (from-to)25-28
Number of pages4
JournalComputational Geometry: Theory and Applications
Volume30
Issue number1
DOIs
Publication statusPublished - 2005
Externally publishedYes

Cite this