{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19205"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19205","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Intersection representations of graphs and digraphs","abstract":"A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We prove that an interval digraph is a unit interval digraph if and only if its adjacency matrix is free of six forbidden submatrices: three 3 by 4 matrices and their transposes.","abstract_html":"A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We prove that an interval digraph is a unit interval digraph if and only if its adjacency matrix is free of six forbidden submatrices: three 3 by 4 matrices and their transposes.","abstract_has_math":false,"creators":["Lin, In-Jen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:00:07Z","date_published":"2011-05-07T12:00:07Z","updated_at":"2026-07-22T22:25:12Z","subjects":["Mathematics","Operations Research","Computer Science"],"languages":["eng"],"rights":["Copyright 1994 Lin, In-Jen"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9416396","(UMI)AAI9416396"],"render_values":[{"text":"AAI9416396","href":null,"code":true},{"text":"(UMI)AAI9416396","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19205","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B."]},{"key":"dc:creator","label":"Author","values":["Lin, In-Jen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:00:07Z","10000-01-01","1994"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Operations Research","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1994 Lin, In-Jen"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9416396","(UMI)AAI9416396","http://hdl.handle.net/2142/19205"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We prove that an interval digraph is a unit interval digraph if and only if its adjacency matrix is free of six forbidden submatrices: three 3 by 4 matrices and their transposes.","We consider a hierarchy of four classes of interval digraphs. For each class, we provide a forbidden submatrix characterization for membership in the next class. In particular, we prove that a digraph in the ith class belongs to the next smaller class if and only if its adjacency matrix contains no submatrix in the collection we list. The largest class is that of all interval digraphs; the smallest is the class of unit interval digraphs. As a corollary, we obtain a second proof of the result described in the first paragraph.","The leafage of a chordal graph is the minimum number of leaves in a host tree in which the graph has an intersection representation by subtrees. We obtain upper and lower bounds on the leafage in terms of other parameters and compute the leafage on special classes of graphs. We use various new observations about chordal graphs and families of subtrees of a tree.","\"We extend the idea of subtree representations of graphs to digraphs. Unlike undirected graphs, every directed graph does have a subtree representation, hence we can define the leafage of a digraph to be the minimum number of leaves in a host tree T in any subtree representation. A catch representation for a digraph D is a subtree representation in which each sink set $T\\sb{v}$ is restricted to be a singleton vertex; the source tree \"\"catches\"\" the singletons assigned to its successors. The catch leafage of a digraph D is the minimum number of leaves in the host tree in any catch representation of D. We study upper and lower bounds for the leafage and catch leafage and show that the bounds are the best possible, but can be arbitrarily weak.\"","Made available in DSpace on 2011-05-07T12:00:07Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9416396.pdf: 4202838 bytes, checksum: 15609330f77571e3a745829f7f10cd22 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:35:22Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:55-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Intersection representations of graphs and digraphs"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B."],"dc:creator":["Lin, In-Jen"],"dc:date":["2011-05-07T12:00:07Z","10000-01-01","1994"],"dc:description":["A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We prove that an interval digraph is a unit interval digraph if and only if its adjacency matrix is free of six forbidden submatrices: three 3 by 4 matrices and their transposes.","We consider a hierarchy of four classes of interval digraphs. For each class, we provide a forbidden submatrix characterization for membership in the next class. In particular, we prove that a digraph in the ith class belongs to the next smaller class if and only if its adjacency matrix contains no submatrix in the collection we list. The largest class is that of all interval digraphs; the smallest is the class of unit interval digraphs. As a corollary, we obtain a second proof of the result described in the first paragraph.","The leafage of a chordal graph is the minimum number of leaves in a host tree in which the graph has an intersection representation by subtrees. We obtain upper and lower bounds on the leafage in terms of other parameters and compute the leafage on special classes of graphs. We use various new observations about chordal graphs and families of subtrees of a tree.","\"We extend the idea of subtree representations of graphs to digraphs. Unlike undirected graphs, every directed graph does have a subtree representation, hence we can define the leafage of a digraph to be the minimum number of leaves in a host tree T in any subtree representation. A catch representation for a digraph D is a subtree representation in which each sink set $T\\sb{v}$ is restricted to be a singleton vertex; the source tree \"\"catches\"\" the singletons assigned to its successors. The catch leafage of a digraph D is the minimum number of leaves in the host tree in any catch representation of D. We study upper and lower bounds for the leafage and catch leafage and show that the bounds are the best possible, but can be arbitrarily weak.\"","Made available in DSpace on 2011-05-07T12:00:07Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9416396.pdf: 4202838 bytes, checksum: 15609330f77571e3a745829f7f10cd22 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:35:22Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:55-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9416396","(UMI)AAI9416396","http://hdl.handle.net/2142/19205"],"dc:language":["eng"],"dc:rights":["Copyright 1994 Lin, In-Jen"],"dc:subject":["Mathematics","Operations Research","Computer Science"],"dc:title":["Intersection representations of graphs and digraphs"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:12Z"}