Intersection graphs of L-shapes and segments in the plane

详细信息    查看全文

• 作者：Stefan Felsner^a ; ^{felsner@math.tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Kolja Knauer^b ; ^{kolja.knauer@lif.univ-mrs.fr" class="auth_mail" title="E-mail the corresponding author} ; George B. Mertzios^c ; ^{george.mertzios@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Torsten Ueckerdt^d ; ^{torsten.ueckerdt@kit.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Intersection graphs ; Segment graphs ; Co-planar graphs ; kk-bend VPGVPG-graphs ; Planar 3-trees
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 June 2016
• 年：2016
• 卷：206
• 期：Complete
• 页码：48-55
• 全文大小：478 K

文摘

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">, mmlsi46" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si46.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=205ef0a975f60149046cce01417dd572" title="Click to view the MathML source">mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx2.jpg">,mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx3.jpg">mathContainer hidden">mathCode"><math altimg="si46.gif" overflow="scroll"><mtext>mtext><mo>,mo><mtext>mtext>math> and mmlsi47" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si47.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=939a53f2ef37cfc2cd80360ac4d6eed7" title="Click to view the MathML source">mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx4.jpg">mathContainer hidden">mathCode"><math altimg="si47.gif" overflow="scroll"><mtext>mtext>math>. A mmlsi48" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si48.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=bc07445056c89fd0a3e6c96e0227c59d" title="Click to view the MathML source">kmathContainer hidden">mathCode"><math altimg="si48.gif" overflow="scroll"><mi>kmi>math>-bend path is a simple path in the plane, whose direction changes mmlsi48" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si48.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=bc07445056c89fd0a3e6c96e0227c59d" title="Click to view the MathML source">kmathContainer hidden">mathCode"><math altimg="si48.gif" overflow="scroll"><mi>kmi>math> times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">, an mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg"> or mmlsi47" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si47.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=939a53f2ef37cfc2cd80360ac4d6eed7" title="Click to view the MathML source">mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx2.jpg">mathContainer hidden">mathCode"><math altimg="si47.gif" overflow="scroll"><mtext>mtext>math>, a mmlsi48" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si48.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=bc07445056c89fd0a3e6c96e0227c59d" title="Click to view the MathML source">kmathContainer hidden">mathCode"><math altimg="si48.gif" overflow="scroll"><mi>kmi>math>-bend path, or a segment, then this graph is called an {mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">}-graph, {mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">,mmlsi47" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si47.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=939a53f2ef37cfc2cd80360ac4d6eed7" title="Click to view the MathML source">mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx2.jpg">mathContainer hidden">mathCode"><math altimg="si47.gif" overflow="scroll"><mtext>mtext>math>}-graph, mmlsi53" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si53.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=cd50822141122f79671cde8fb8c55934" title="Click to view the MathML source">B_kmathContainer hidden">mathCode"><math altimg="si53.gif" overflow="scroll"><msub><mrow><mi>Bmi>mrow><mrow><mi>kmi>mrow>msub>math>-mmlsi17" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si17.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=b8135365a3e46fc4ea177bd035580f97" title="Click to view the MathML source">VPGmathContainer hidden">mathCode"><math altimg="si17.gif" overflow="scroll"><mo>VPGmo>math>-graph or mmlsi55" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si55.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=201494e2751c0048bba8cfebd830e60a" title="Click to view the MathML source">SEGmathContainer hidden">mathCode"><math altimg="si55.gif" overflow="scroll"><mo>SEGmo>math>-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">,mmlsi47" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si47.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=939a53f2ef37cfc2cd80360ac4d6eed7" title="Click to view the MathML source">mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx2.jpg">mathContainer hidden">mathCode"><math altimg="si47.gif" overflow="scroll"><mtext>mtext>math>}-graph is a mmlsi55" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si55.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=201494e2751c0048bba8cfebd830e60a" title="Click to view the MathML source">SEGmathContainer hidden">mathCode"><math altimg="si55.gif" overflow="scroll"><mo>SEGmo>math>-graph, we investigate several known subclasses of mmlsi55" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si55.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=201494e2751c0048bba8cfebd830e60a" title="Click to view the MathML source">SEGmathContainer hidden">mathCode"><math altimg="si55.gif" overflow="scroll"><mo>SEGmo>math>-graphs and show that they are {mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">}-graphs, or mmlsi53" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si53.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=cd50822141122f79671cde8fb8c55934" title="Click to view the MathML source">B_kmathContainer hidden">mathCode"><math altimg="si53.gif" overflow="scroll"><msub><mrow><mi>Bmi>mrow><mrow><mi>kmi>mrow>msub>math>-mmlsi17" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si17.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=b8135365a3e46fc4ea177bd035580f97" title="Click to view the MathML source">VPGmathContainer hidden">mathCode"><math altimg="si17.gif" overflow="scroll"><mo>VPGmo>math>-graphs for some small constant mmlsi48" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si48.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=bc07445056c89fd0a3e6c96e0227c59d" title="Click to view the MathML source">kmathContainer hidden">mathCode"><math altimg="si48.gif" overflow="scroll"><mi>kmi>math>. We show that all planar 3-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are {mg class="imgLazyJSB inlineImage" height="8" width="5" alt="Full-size image (25 K)" title="Full-size image (25 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16300154-fx1.jpg">}-graphs. Furthermore we show that complements of planar graphs are mmlsi62" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si62.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=feaa3f01f4588d8ade57369f73b56030" title="Click to view the MathML source">B₁₇mathContainer hidden">mathCode"><math altimg="si62.gif" overflow="scroll"><msub><mrow><mi>Bmi>mrow><mrow><mn>17mn>mrow>msub>math>-mmlsi17" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si17.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=b8135365a3e46fc4ea177bd035580f97" title="Click to view the MathML source">VPGmathContainer hidden">mathCode"><math altimg="si17.gif" overflow="scroll"><mo>VPGmo>math>-graphs and complements of full subdivisions are mmlsi64" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si64.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=86d525f450a2126494f2ad5663d8a65d" title="Click to view the MathML source">B₂mathContainer hidden">mathCode"><math altimg="si64.gif" overflow="scroll"><msub><mrow><mi>Bmi>mrow><mrow><mn>2mn>mrow>msub>math>-mmlsi17" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300154&_mathId=si17.gif&_user=111111111&_pii=S0166218X16300154&_rdoc=1&_issn=0166218X&md5=b8135365a3e46fc4ea177bd035580f97" title="Click to view the MathML source">VPGmathContainer hidden">mathCode"><math altimg="si17.gif" overflow="scroll"><mo>VPGmo>math>-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.