home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10297 < prev    next >
Encoding:
Internet Message Format  |  1992-08-14  |  2.1 KB
  1. Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!camcus!crb11
  2. From: crb11@cus.cam.ac.uk (Colin Bell)
  3. Newsgroups: sci.math
  4. Subject: Graph Theory problem
  5. Message-ID: <1992Aug15.021435.4885@infodev.cam.ac.uk>
  6. Date: 15 Aug 92 02:14:35 GMT
  7. Sender: news@infodev.cam.ac.uk (USENET news)
  8. Organization: U of Cambridge, England
  9. Lines: 37
  10. Nntp-Posting-Host: apus.cus.cam.ac.uk
  11.  
  12. 01234567890123456789012345678901234567890123456789012345678901234567890123456789
  13. A friend (Adam Chalcraft) posed the following problem:
  14.  
  15. 1. Given a connected planar graph in which all regions (not including the outside region) are triangles, is it possible to represent it by (disjoint) rectangles such that two rectangles meet at an edge iff the points that they represent meet.
  16.  
  17. For example,
  18.       C                                      --- --- -------                  
  19.        o                                    !   !   !   C   !
  20.       / \                                   !   !    -------
  21. A   B/   \ D   E                            ! A ! B !   D   !
  22. o---o-----o---o        is represented by    !   !    -------
  23.      \   /   /                              !   !   ! F ! E !
  24.       \ !   /                                --- --- --- ---
  25.        \!  /
  26.         o--
  27.         F
  28.  
  29. 2. If 1 is possible for a given graph, is it possible to do it so that the rectangles put together form a rectangle as in the above example.
  30.  
  31. Note that there are trivial counterexamples to both 1 and 2: for example in 1, if you have an internal point of degree <=3 then it fails, since its rectangle must have at least  four distinct neighbouring rectangles.
  32.  
  33. For 2, consider the graph:
  34.  
  35.   o
  36.   !
  37. o-o-o
  38.   !
  39.   o   
  40.  
  41. It clearly has a representation (one large square with a small square attached to each side, for example) but no rectangular representation.
  42.  
  43. Both problems have rather nice solutions and quite a nice proof, which I will email to people on request.
  44.  
  45. Now a question for the experts: is this problem or related ones known in the literature? If so, please send me a reference or other information.
  46. -- 
  47. Colin Bell, CRB11@CUS.CAM.UK.AC
  48. Department of Pure Mathematics, University of Cambridge.
  49.