This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P4's, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations are presented. The recognition algorithm also produces, as a by-product, a data structure which can be used for solving the four classic graph optimization problems in linear time.
","abstract_html":"<p>This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P<sub>4</sub>'s, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations are presented. The recognition algorithm also produces, as a by-product, a data structure which can be used for solving the four classic graph optimization problems in linear time.</p>","abstract_has_math":false,"creators":["Jamison, Beverly"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Stephan Olariu","Kurt Maly","John Tweed"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1989,"date_issued":"1989-07-01T07:00:00Z","date_published":"1989-07-01T07:00:00Z","updated_at":"2026-07-24T03:35:15Z","subjects":["Graphs","Graph classification","Isomorphism","Computer Sciences"],"languages":[],"rights":["In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.odu.edu/computerscience_etds/112","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Stephan Olariu","Kurt Maly","John Tweed"]},{"key":"dc:creator","label":"Author","values":["Jamison, Beverly"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-09-25T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graphs","Graph classification","Isomorphism","Computer Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.odu.edu/computerscience_etds/112"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P4's, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations are presented. The recognition algorithm also produces, as a by-product, a data structure which can be used for solving the four classic graph optimization problems in linear time.
"]},{"key":"dc:title","label":"Title","values":["On the Unique Tree Representation of Graphs"]}]}],"canonical_facts":{"dc:contributor":["Stephan Olariu","Kurt Maly","John Tweed"],"dc:creator":["Jamison, Beverly"],"dc:date.available":["2019-09-25T07:00:00Z"],"dc:description.abstract":["This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P4's, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations are presented. The recognition algorithm also produces, as a by-product, a data structure which can be used for solving the four classic graph optimization problems in linear time.
"],"dc:identifier":["https://digitalcommons.odu.edu/computerscience_etds/112"],"dc:rights":["In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
"],"dc:subject":["Graphs","Graph classification","Isomorphism","Computer Sciences"],"dc:title":["On the Unique Tree Representation of Graphs"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T03:35:15Z"}