Sachverhalt:
A.
A._ (geb. 1966, französischer Staatsangehöriger) und B._ (geb. 1973, österreichische Staatsangehörige) heirateten am 14. Januar 2011. Sie haben die gemeinsamen Kinder C._ (geb. 2010) und D._ (geb. 2011). Über die Jahreswende 2011/2012 trennten sich die Ehegatten. Auf ein Eheschutzbegehren der Ehefrau hin genehmigte die Familienrichterin des Kreisgerichts St. Gallen eine Vereinbarung der Ehegatten über die Kinderbelange und den Unterhalt.
B.
Am 18. September 2013 verlangten die Eheleute gemeinsam die Scheidung und am 25. April 2014 stellte die Ehefrau ein Gesuch um Erlass vorsorglicher Massnahmen. Mit Urteil vom 7. Juli 2014 schied das Kreisgericht St. Gallen die Ehe zwischen den Parteien. Es beliess den Eltern das gemeinsame Sorgerecht, teilte aber die Kinder insofern der Mutter zu, als es sie unter deren alleinige Obhut stellte und auch bestimmte, dass sie bei ihr wohnen. Dem Vater wurde ein Besuchsrecht für jedes zweite Wochenende von Samstag, 9.00 Uhr, bis Sonntag, 18.00 Uhr, sowie ein Ferienrecht von zwei Wochen pro Jahr eingeräumt. Im Weiteren erteilte das Gericht der Mutter die Erlaubnis, den Aufenthaltsort der Kinder nach Graz zu verlegen. Für die Zeit ab dem Umzug wurde dem Vater das Recht eingeräumt, die Kinder jedes erste Wochenende im Monat von Freitag, 8.00 Uhr, bis Sonntag, 18.00 Uhr, in Graz zu besuchen, wobei er jeweils zwei Wochen vorher mitzuteilen habe, ob er das Besuchsrecht wahrnehme; die Mutter wurde verpflichtet, die Kinder alle drei Monate (Februar, Mai, August, November) jeweils am dritten Wochenende des Monats nach U._ zu bringen, so dass der Vater mit den Kindern die Zeit von Freitag, 9.30 Uhr, bis Sonntag, 14.00 Uhr, verbringen könne. Das Ferienrecht wurde für die Zeit nach dem Umzug nach Graz unverändert auf zwei Wochen pro Jahr festgesetzt. Ferner ordnete das Kreisgericht eine Beistandschaft nach Art. 308 Abs. 1 und 2 ZGB an. Zudem regelte es den Unterhalt für die Ehefrau und die Kinder, und zwar separat für die Zeit in der Schweiz und für die Zeit ab dem Umzug nach Graz. Gleichzeitig traf das Gericht für die Zeit bis zur Rechtskraft des Scheidungsurteils als Massnahme die gleiche Regelung wie im Scheidungsurteil.
Dagegen erhob A._ Berufung. Mit Entscheid vom 29. April 2015 bestätigte das Kantonsgericht St. Gallen die erstinstanzliche Regelung, insbesondere die Kinderzuteilung und die Erlaubnis, den Wohnsitz der Kinder nach Graz zu verlegen.
C.
Gegen den kantonsgerichtlichen Entscheid hat A._ am 1. Juni 2015 eine Beschwerde in Zivilsachen erhoben. Er verlangt die Abweisung des Begehrens um Erlaubnis zur Verlegung des Aufenthaltsortes der Kinder, ein ausgedehnteres Besuchsrecht (jedes zweite Wochenende bereits ab Freitagabend statt Samstagmorgen sowie alternierend an Ostern, Auffahrt, Pfingsten und Weihnachten) und die Neuverteilung der Prozesskosten, eventualiter die Rückweisung der Sache an das Kantonsgericht zur neuen Entscheidung in den betreffenden Punkten. Ferner verlangt der Beschwerdeführer die unentgeltliche Rechtspflege. Mit Präsidialverfügung vom 9. Juli 2015 wurde die aufschiebende Wirkung erteilt. Mit Schreiben vom 13. November 2015 beantragt das Kantonsgericht die Abweisung der Beschwerde. Mit Vernehmlassung vom 3. Dezember 2015 beantragt die Mutter ebenfalls die Abweisung der Beschwerde, soweit darauf einzutreten sei; ferner verlangt auch sie die unentgeltliche Rechtspflege.

Erwägungen:
1.
Angefochten ist der kantonal letztinstanzliche Entscheid in einer Zivilsache über nicht vermögensrechtliche Streitpunkte; die Beschwerde in Zivilsachen steht offen (Art. 72 Abs. 1, Art. 75 Abs. 1 und Art. 90 BGG).
Zulässig sind rechtliche Vorbringen im Sinn von Art. 95 f. BGG. Hingegen ist die obergerichtliche Sachverhaltsfeststellung für das Bundesgericht grundsätzlich verbindlich (<ref-law>). Wird eine Sachverhaltsfeststellung beanstandet, muss in der Beschwerdeschrift mit klar und detailliert erhobenen und soweit möglich belegten Rügen (<ref-ruling> E. 2.2 S. 246) dargetan werden, inwiefern diese Feststellung offensichtlich unrichtig und damit willkürlich ist und inwiefern die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 i.V.m. <ref-law>; <ref-ruling> E. 1.5 S. 129 f.; <ref-ruling> E. 4.2 S. 234).
2.
Umstritten ist in erster Linie, ob der Mutter zu erlauben ist, den Aufenthaltsort der Kinder nach Graz zu verlegen. Dies richtet sich nach <ref-law>, welcher auf den 1. Juli 2014 in Kraft getreten ist.
2.1. Die kantonalen Gerichte sind von der Tatsache ausgegangen, dass die Kinder hauptsächlich von der Mutter betreut werden, und haben erwogen, dass diesfalls die Verlegung des Aufenthaltsortes nur in Ausnahmefällen zu verweigern sei. Zwar könne das Besuchsrecht des Vaters durch die langen Reisewege weniger oft ausgeübt werden und würden spontane Besuche unmöglich. Auf der anderen Seite habe die Mutter ihren Umzugswunsch gut begründet. Sie wolle nach der Trennung zu ihren Wurzeln und in ihr Heimatland zurückkehren, zumal sie sich in der Schweiz nicht integriert fühle. Es sei nachvollziehbar, dass sie in Graz punkto Arbeitsbedingungen (Gastgewerbe), subjektives Wohlbefinden und Kinderfremdbetreuung bessere Perspektiven sehe. Im Übrigen seien dort ähnliche Lebensbedingungen zu erwarten und für die Kinder seien keine Gefahren ersichtlich, zumal sie österreichische Staatsbürger seien und es um das gleiche sprachliche Umfeld gehe. Was den Vater anbelange, zeige sich auch in den neusten Eingaben kein besonders inniges und vertrautes Verhältnis mit den Kindern. Die gelebte Betreuungssituation würde sich mit einem Wegzug nicht verändern; er verlange denn auch weiterhin "bloss" ein übliches Besuchsrecht und wolle keine namhaften Betreuungsanteile übernehmen. Es wäre deshalb unangemessen, der Mutter den Wegzug zu verbieten; vielmehr sei das Besuchsrecht des Vaters an die beabsichtigte neue Situation anzupassen.
2.2. Der Vater macht beschwerdeweise geltend, die Kinder hätten das Recht auf Betreuung durch beide Elternteile und der Kontakt dürfe nicht durch einen Umzug faktisch vereitelt werden. Die Mutter habe den Umzug nicht sorgfältig geplant und überlegt; insbesondere könne sie für Graz weder eine Arbeit noch eine Wohnung nachweisen. Es sei völlig willkürlich, wenn das Kantonsgericht festgehalten habe, sie könne dies aufgrund der eingelegten Rechtsmittel nicht. Es sei im Übrigen zynisch zu sagen, Graz biete gute Arbeits-, Sozial- und Wohnverhältnisse; das Kindeswohl stehe bereits dann in Frage, wenn die Arbeits-, Wohn- und Betreuungssituation am neuen Ort nicht vollständig klar sei, zumal die Mutter in U._ erwiesenermassen über eine Arbeit und eine Wohnung verfüge. Es sei auch nicht nachvollziehbar, weshalb sie sich trotz ihres langjährigen Aufenthaltes in der Schweiz nicht integriert fühle, er selbst sei ja auch Ausländer, sogar mit anderer Muttersprache, und habe sich problemlos integrieren können. Die Mutter verfüge in Graz nicht mehr über viele soziale Kontakte und es sei fraglich, ob sie sich dort ein Netz aufbauen könne. Sodann verfüge sie nicht über die nötige Bindungstoleranz; die gegenteiligen Feststellungen beruhten auf willkürlicher Beweiswürdigung. Im Übrigen werde sein Besuchsrecht mit einer Bewilligung des Umzuges in unzulässiger Weise beschnitten. Auch die Tatsache einer binationalen Ehe mache den Umzug nicht zulässig. Das Kantonsgericht missachte das Kindeswohl, wenn es den Umzug bewillige, zumal zweifelsfrei feststehen müsste, dass der Umzug wohl überlegt und nicht rechtsmissbräuchlich sei.
Die Mutter bringt vernehmlassungsweise vor, der Umzug in ihre Heimat sei wohl überlegt. Sie könne aber keinen Arbeits- und Mietvertrag unterzeichnen oder die Kinder in der Schule anmelden, solange aufgrund der väterlicherseits eingereichten Rechtsmittel nicht feststehe, wann sie ausreisen könne. Der Vater verlange deshalb Beweise, welche objektiv nicht erbracht werden könnten. Es gehe nicht um ein entlegenes, exotisches oder gefährliches Land, weshalb die Befürchtungen des Vaters unbegründet seien; die Kinder wären in Graz ebenso gut versorgt, beschult und betreut. Im Übrigen seien für sie die Arbeitsbedingungen in Graz besser; sie verliere ihre Arbeitsstelle in der Schweiz und werde ab 2016 zur Sozialhilfebezügerin, soweit sie nichts Neues finde.
2.3. Mit Bundesgesetz vom 21. Juni 2013, in Kraft getreten auf 1. Juli 2014 (AS 2014 357), wurde die elterliche Sorge und in diesem Zusammenhang auch das Aufenthaltsbestimmungsrecht betreffend die Kinder einer Revision unterzogen. Das neue Recht statuiert als allgemeinen Grundsatz die gemeinsame elterliche Sorge, auch für geschiedene oder nicht miteinander verheiratete Eltern (zu den Ausnahmen vgl. <ref-ruling>). Während unter altem Recht das Aufenthaltsbestimmungsrecht als Teil des Obhutsrechtes aufzufassen war (vgl. <ref-ruling>), bestimmt die Gesetzesnovelle, dass die elterliche Sorge das Recht einschliesst, den Aufenthaltsort des Kindes zu bestimmen (<ref-law>). Üben die Eltern die elterliche Sorge gemeinsam aus und will ein Elternteil den Aufenthaltsort des Kindes wechseln, so bedarf dies der Zustimmung des andern Elternteils oder der Entscheidung des Gerichts bzw. der Kindesschutzbehörde, wenn der neue Aufenthaltsort im Ausland liegt oder der Wechsel des Aufenthaltsortes erhebliche Auswirkungen auf die Ausübung der elterlichen Sorge und den persönlichen Verkehr durch den andern Elternteil hat (<ref-law>).
Grundgedanke dieser Norm ist, dass die Beziehung zu den Elternteilen vom Aufenthaltsort des Kindes abhängt und deshalb keiner alleine diesen verlegen können soll, wenn dadurch die Ausübung der Elternrechte des andern erheblich betroffen werden (vgl. Botschaft des Bundesrates vom 16. November 2011, BBl 2011 9107 f.). Für die transnationale Verlegung des Aufenthaltsortes war zudem die Überlegung wesentlich, dass damit ein Wechsel der Jurisdiktion in Bezug auf die Kinderbelange verbunden ist (vgl. Art. 5 des Haager Kindesschutzübereinkommens, HKsÜ, SR 0.211.231.011, und Art. 5 Abs. 2 lit. a und c des Lugano-Übereinkommens, LugÜ, SR 0.275.12), weshalb unabhängig von der Distanz des neuen Aufenthaltsortes und dem konkreten Einfluss auf die Ausübung der elterlichen Sorge die Zustimmung des anderen Elternteils bzw. des Gerichtes oder der Kindesschutzbehörde erforderlich sein soll (Botschaft, BBl 2011 9108).
Die materielle Regelungszuständigkeit für die Fragen der elterlichen Sorge, der Obhut bzw. der Betreuung, des persönlichen Verkehrs und des Aufenthaltsbestimmungsrechtes obliegt bislang ausschliesslich dem nationalen Gesetzgeber. Zwar gibt es in diesem Sachbereich auf internationaler Ebene verschiedene Übereinkommen; diese betreffen aber einzig die Zuständigkeiten, das anwendbare Recht und die Urteilsanerkennung bzw. -vollstreckung. Sodann bestehen Rechtshilfeabkommen bei internationalen Kindesentführungen, namentlich das Haager Entführungsübereinkommen (HKÜ, SR 0.211.230.02). Dieses regelt die Folgen der Verletzung einer dem anderen Elternteil ausschliesslich oder gemeinsam zustehenden Sorgerechtsposition (Art. 3 HKÜ) bzw. des Aufenthaltsbestimmungsrechtes über das Kind (Art. 5 HKÜ). Wem in materieller Hinsicht das Aufenthaltsbestimmungsrecht zusteht, so dass es zu einer widerrechtlichen Verletzung im Sinn von Art. 3 und 5 HKÜ und somit zu einer Entführung im Sinn des HKÜ kommen kann, ist jedoch zwangsläufig nicht im Übereinkommen normiert; vielmehr bemisst sich dies nach dem Recht, welches gemäss dem internationalen Privatrecht im Staat des gewöhnlichen Aufenthaltes des Kindes vor dem widerrechtlichen Verbringen Anwendung findet (vgl. Urteil 5A_764/2009 vom 11. Januar 2010 E. 3.1).
Was die materiellen Aspekte anbelangt, gibt es auf internationaler Ebene im Zusammenhang mit dem Aufenthaltsbestimmungsrecht und dem Wegzug von Kindern (sog. Relocation) erst verschiedene Bemühungen für eine mögliche künftige Vereinheitlichung, welche indes für den nationalen Gesetzgeber bislang in keiner Hinsicht verbindlich sind. Zu nennen ist die sog. Washingtoner Erklärung (Washington Declaration on International Family Relocation), welche von der internationalen Richterkonferenz (International Judicial Conference) im März 2010 verabschiedet wurde. Darin wird ein Katalog von Entscheidungskriterien aufgeführt, wenn sich die Eltern nicht über den Aufenthaltsort des Kindes im Wegzugsfall einigen können. Unter anderem werden die Möglichkeit der Aufrechterhaltung einer Beziehung zu beiden Elternteilen, die Wünsche des Kindes, die Vorschläge der Eltern, die Gründe für den Wegzug, die Erziehungskontinuität, die vorbestehende Sorge- und Umgangsrechtsregelung, die Vollstreckbarkeit der Vereinbarung und die Mobilität der Familienmitglieder als mögliche Kriterien genannt, wobei zwischen diesen ausdrücklich keine Hierarchie bestehen soll. Zu erwähnen ist weiter die Empfehlung des Europarates vom Mai 2011 betreffend Kinderrechte (Recommendation on the Rights and Legal Status of Children and Parental Responsibilities), deren "Principle 31" sich der "Residence and Relocation" widmet. Die darin enthaltenen Empfehlungen gehen dahin, dass die Staaten geeignete Mechanismen wie die Mediation fördern und im Streitfall die zuständige Behörde entscheiden soll, soweit das nationale Recht nichts anderes vorsieht; dabei sollte in erster Linie auf das Kindeswohl abgestellt, im Übrigen aber auch alle weiteren relevanten Faktoren gebührend berücksichtigt werden. Schliesslich sind auf der Haager Ebene Arbeiten im Gang, Grundlagen im Bereich der Relocation zu schaffen. Im Januar 2012 veröffentlichte das Ständige Büro (Permanent Bureau) der Haager Konferenz einen Vorbericht (Preliminary Note on International Family Relocation), in welchem es empfahl, dass die Spezialkommission (Special Commission) weitere Untersuchungen zum Thema anstellt (Preliminary Note, Rz. 83). Diese hielt im Januar 2012 fest, dass die Washingtoner Erklärung eine taugliche Basis für kommende Arbeiten bilde und weitere Grundlagenarbeit zu erbringen sei (Conclusions and Recommendations, Rz. 83 f.). Der erwähnte Vorbericht des Ständigen Büros hebt hervor, dass sich die jüngere sozio-psychologische Forschung keineswegs einig sei, ob dem Kindeswohl mit umfangreichem Kontakt zu beiden Elternteilen (was die Erlaubnis des Wegzuges tendenziell ausschliesst) am besten Rechnung getragen sei oder ob in erster Linie die Qualität des Kontaktes zum hauptbetreuenden Elternteil (was den Wegzug tendenziell erlaubt) für das Gedeihen des Kindes verantwortlich sei (Preliminary Note, Rz. 32). Weiter hält der Vorbericht fest, dass nur wenige Staaten die Relocation konkret geregelt und spezifische Verfahrensnormen aufgestellt hätten (Preliminary Note, Rz. 44 f.). Etliche Staaten gingen das Problem unter dem Aspekt des Sorge- bzw. Obhutsrechts und dessen Abänderung an (Preliminary Note, Rz. 46). Der Vorbericht weist ferner darauf hin, dass für den Ausgang des Wegzugsverfahrens entscheidend sein könne, ob bestimmte Vermutungen oder Beweislastregeln gälten oder die Beweise frei zu würdigen seien oder sogar die Offizialmaxime gelte (Preliminary Note, Rz. 48 ff.).
Aus dem Gesagten ergibt sich, dass der nationale Gesetzgeber dazu aufgerufen, aber inhaltlich frei ist, das Aufenthaltsbestimmungsrecht in Bezug auf die Kinder, insbesondere im Zusammenhang mit der Frage des Wegzuges, zu regeln. Wie die mit der Gesetzesnovelle vom 21. Juni 2013 erfolgte Normierung aussieht, ist nachfolgend darzustellen.
2.4. Im Entwurf des Bundesrates war <ref-law> dahingehend formuliert, dass der Wegzug des anderen Elternteiles und des Kindes zustimmungsbedürftig sei ("Üben die Eltern die elterliche Sorge gemeinsam aus und will ein Elternteil seinen Aufenthaltsort oder jenen des Kindes wechseln, so bedarf dies der Zustimmung..."). Die Botschaft des Bundesrates vom 16. November 2011 betonte diesbezüglich, dass auch ein Ortswechsel nur des Elternteiles allein (insbesondere auch der Ortswechsel des nicht hauptbetreuenden Elternteils) des elterlichen Konsenses bedürfe (BBl 2011 9107).
Dass der Umzug einer erwachsenen Person aufgrund der Tatsache eines gemeinsamen Kindes von der Zustimmung einer anderen Person abhängig sein sollte, stiess in der Vernehmlassung auf Kritik und führte in der parlamentarischen Beratung zu Kontroversen (vgl. die nationalrätliche Debatte, AB 2012 N 1652 ff., und die ständerätliche Debatte, AB 2013 S 12 ff.), weil damit eine Anzahl von verfassungsmässigen Rechten (insbesondere die Niederlassungsfreiheit, <ref-law>, aber auch die persönliche Freiheit und die Gewerbefreiheit, vgl. TUOR/SCHNYDER/JUNGO, Das Schweizerische Zivilgesetzbuch, 14. Aufl. 2015, S. 514), beeinträchtigt worden wären.
Die vorberatende Kommission des Ständerates bzw. der Ständerat trug der geäusserten Kritik dahingehend Rechnung (vgl. AB 2013 S 13 ff.), dass in Abs. 2 die Zustimmungsbedürftigkeit auf die Veränderung des Aufenthaltsortes des Kindes beschränkt und <ref-law> im Übrigen um die Absätze 3-5 ergänzt wurde (Informationspflicht bei alleinigem Sorgerecht; Informationspflicht in Bezug auf den eigenen Wohnsitzwechsel; Verständigung bzw. Entscheid über die Anpassung der Sorge, der Obhut, des persönlichen Verkehrs und des Unterhaltes). Der Nationalrat stimmte dieser Fassung von <ref-law> zu (AB 2013 N 704). Bundesrätin Sommaruga nahm im Ständerat zur Kritik an der ursprünglichen Fassung des Entwurfes wie folgt Stellung: Der Zweck der Norm bestehe in der Tat nicht darin, den Umzug eines Elternteils zu verhindern, sondern die Eltern dazu zu bewegen, vor einem Umzug dessen Auswirkungen auf die Ausübung der gemeinsamen elterlichen Sorge zu prüfen und wenn nötig die bestehende Regelung über die Kinderbelange anzupassen. Die ständerätliche Kommission habe sich wirklich bemüht, eine Lösung zu finden, die dieses Anliegen etwas besser zum Ausdruck bringe, und sie [Bundesrätin Sommaruga] dürfe heute sagen, dass dies der Kommission sehr gut gelungen sei (AB 2013 S 14).
2.5. Was die Auslegung von <ref-law> und dabei insbesondere die für die Wegzugsfrage relevanten Kriterien anbelangt, bildet der mit der verabschiedeten Fassung von Abs. 2 bewusst getroffene Entscheid des Gesetzgebers, dass die Niederlassungs- bzw. die Bewegungsfreiheit der Elternteile zu respektieren ist, den Ausgangspunkt.
Diese gesetzgeberische Wertung ist nicht nur im Zusammenhang mit den verfassungsmässigen Rechten der Eltern (Niederlassungsfreiheit, persönliche Freiheit, Gewerbefreiheit), sondern ebenso im Kontext mit dem Grundsatz der Familienautonomie, welcher das Zivilgesetzbuch prägt, zu lesen. Es besteht ein allgemeiner gesellschaftlicher Konsens, dass der Staat grundsätzlich nicht in die Lebensplanung der Eltern eingreifen soll. Dies gilt auch für die Aufenthaltsfrage der Kinder. Familien können beliebig herumziehen oder auswandern; es bestehen keinerlei Genehmigungspflichten, und der Staat enthält sich selbst dann einer Intervention, wenn die damit einhergehende Relocation des Kindes seinem Wohl abträglich ist oder gegen dessen ausdrücklichen Willen geschieht. Die Respektierung der privatautonomen elterlichen Entscheidung durch den Staat beruht letztlich auf der Annahme, dass die Eltern ihre Verantwortung wahrnehmen und am besten dazu berufen sind, die Maxime des Kindeswohles mit Inhalt zu füllen (vgl. sinngemäss COESTER-WALTJEN, Relocation - from Theory to Practice, in: iFamZ 2012, S. 312). Es wäre wenig einsichtig, weshalb für den Fall des elterlichen Dissenses in Bezug auf die Relocation des Kindes die Elternautonomie aufgehoben sein (COESTER-WALTJEN, a.a.O., S. 313) und es zu einer Diskussion über die Motive für den Wegzug und damit zu einer staatlichen "Gesinnungsschnüffelei" (vgl. FASSBIND, Inhalt des gemeinsamen Sorgerechts, der Obhut und des Aufenthaltsbestimmungsrechts im Lichte des neuen gemeinsamen Sorgerechts als Regelfall, in: AJP 2014 S. 699) durch den Richter oder die Kindesschutzbehörde kommen sollte.
Im Zusammenhang mit der Grundrechtsausübung ist schliesslich zu bemerken, dass es keineswegs nur um die Niederlassungsfreiheit, sondern ebenso sehr um die persönliche Freiheit bzw. die Freiheit der Lebensgestaltung an sich geht. Freilich können Betreuungspflichten zu einer Einschränkung dieser Rechte, aber insbesondere auch zu faktischen Schwierigkeiten bei der Ausübung dieser Freiheiten führen; dies ist bei zusammenlebenden Paaren nicht anders als bei alleinerziehenden Eltern. Die Tatsache, dass gemeinsame Kinder vorhanden sind, ist aber kein Grund, die Ausübung von Freiheitsrechten über das Konzept des Gesetzgebers hinaus zu beschneiden. Dies ergibt sich insbesondere auch aus einer Parallelwertung mit anderen familienrechtlichen Instituten, welche auf der Ausübung von Grundfreiheiten beruhen und die Lebensplanung betreffen. Beispielsweise hat der Gesetzgeber die Scheidungsfreiheit nicht beschränkt, nur weil aus der Ehe gemeinsame Kinder hervorgegangen sind; dem Scheidungsbegehren eines Elternteils ist selbst dann stattzugeben, wenn der andere Teil scheidungsunwillig ist oder es der grösste Wunsch der Kinder wäre, dass die Eltern zusammenbleiben. Es wird mit anderen Worten von der sich aus einseitiger Willensausübung ergebenden Scheidungstatsache ausgegangen und als Folge werden die Kinderbelange neu geregelt, wobei das Kindeswohl hierfür die Leitmaxime bildet (<ref-law>). Ebenso wenig ist ein Elternteil daran gehindert, durch das Eingehen einer (neuen) Ehe von seiner Ehefreiheit Gebrauch zu machen, selbst wenn der frühere Partner damit nicht einverstanden ist oder sich die Kinder aus der früheren Beziehung dagegen auflehnen und eine Beeinträchtigung des Kindeswohls zur Debatte steht. Auch hier wird von der sich aus dem Heiratswillen des einen Elternteils ergebenden Tatsache der (Neu-) Verheiratung ausgegangen und sind als Folge gegebenenfalls die Belange der aus der früheren Beziehung stammenden Kinder anzupassen, wiederum unter Beachtung des Kindeswohl als oberster Maxime.
Aus dem gleichen Wertungsgedanken heraus hat der Gesetzgeber, was die Niederlassungsfreiheit der Elternteile anbelangt, den gegenüber dem Gesetzesentwurf geäusserten Bedenken durch eine bewusste Modifikation von <ref-law> Rechnung getragen und dafür gesorgt, dass die Schweiz nicht aufgrund einer "faktischen Residenzpflicht" (vgl. <ref-ruling> E. 3.3 S. 359) zu einem "Müttergefängnis" (vgl. Entscheid des Obergerichtes des Kantons Bern vom 26. Mai 2014, in: FamPra.ch 2015, S. 252) wird. Das bedeutet, dass die - ohnehin kaum justiziablen - Motive des wegziehenden Elternteils grundsätzlich nicht zur Debatte stehen können. Vielmehr ist von der Hypothese auszugehen, dass der eine Elternteil wegzieht (so auch COESTER-WALTJEN, a.a.O., S. 314), und es ist als Folge die Eltern-Kind-Beziehung soweit nötig anzupassen (<ref-law>). Insofern entspricht die vom Gesetzgeber verabschiedete Gesetzesfassung dem, was der deutsche Bundesgerichtshof (BGH) für die internationale Relocation durch richterliche Rechtsfindung festgehalten hat:
In Deutschland finden sich im Gesetz keine die Wegzugsfrage direkt regelnde Normen. Anwendbar ist § 1631 Abs. 1 BGB, wonach die Personensorge das Aufenthaltsbestimmungsrecht für das Kind umfasst, in Verbindung mit § 1671 Abs. 1 BGB, wonach der getrennt lebende Elternteil beantragen kann, dass ihm das Familiengericht die elterliche Sorge oder einen Teil davon allein überträgt. Im Sinne einer Leitentscheidung hat der BGH im Beschluss XII ZB 81/09 vom 28. April 2010 - betreffend einen Wegzug nach Mexiko - festgehalten, dass das Kindeswohl der Massstab sei (Rz. 17). Die verfassungsrechtlich in Art. 2 des Grundgesetzes garantierte allgemeine Handlungsfreiheit des auswanderungswilligen Elternteils bestimme die tatsächliche Ausgangslage, denn für die Beurteilung des Kindeswohls sei nicht davon auszugehen, dass der hauptsächlich betreuende Elternteil mit dem Kind im Inland verbleibe, selbst wenn dies mit dem Kindeswohl am besten zu vereinbaren wäre, sondern dass er seinen Auswanderungswunsch in die Tat umsetze (Rz. 22). Die Motive für den Auswanderungsentschluss stünden nicht zur Überprüfung durch das Gericht; insoweit komme es nicht darauf an, ob der Elternteil triftige Gründe anführen könne (Rz. 23). Die Befugnisse des Gerichtes hätten sich darauf zu konzentrieren, wie sich die Auswanderung auf das Kindeswohl auswirke; verfolge der Elternteil mit der Übersiedlung den Zweck, den Kontakt zum anderen Elternteil zu vereiteln, stehe die Bindungstoleranz und somit die Erziehungseignung in Frage; bei schädlichen Auswirkungen der Auswanderung für das Kind sei die Erziehungseignung in Zweifel zu ziehen und könne sogar ein Entzug des Sorgerechts angebracht sein; bei einem ersichtlich unvernünftigen Vorhaben würden sich für die Kontinuität und die Qualität der Bindung zum Obhutselternteil nachteilige Folgen ergeben und sei das Sorgerecht bei bestehender Erziehungseignung gegebenenfalls dem anderen Elternteil zu übertragen (Rz. 24). Einer Auswanderung stehe nicht ohne weiteres entgegen, dass zum Wohl des Kindes in der Regel der Umgang mit beiden Elternteilen gehöre; auch wenn durch die Auswanderung der Umgang mit dem anderen Elternteil wesentlich erschwert werde, ergebe sich daraus allein weder eine generelle noch eine vermutete Kindeswohlschädlichkeit (Rz. 25). Die Entscheidung des Gerichtes sei nicht durch tatsächliche oder rechtliche Vermutungen eingeengt; zu fragen sei, ob die Auswanderung mit dem hauptbetreuenden Elternteil oder der Verbleib des Kindes beim weiter im Inland ansässigen Elternteil die für das Kindeswohl bessere Lösung sei (Rz. 28). Analog zu den vorstehenden Erwägungen hat der Bundesgerichtshof auch im Entscheid XII ZB 407/10 vom 16. März 2011 argumentiert.
2.6. Ähnliche Überlegungen müssen, wie nachfolgend zu zeigen sein wird, für die Auslegung und Anwendung von <ref-law> gelten. Wie gesagt ist von der Prämisse auszugehen, dass der eine Elternteil in Ausübung seiner Freiheitsrechte wegziehen will. Es ist mithin nicht ein Vorzustand zu perpetuieren, sondern eine neue Situation zu regeln (vgl. FASSBIND, a.a.O., S. 697). Die hierbei aufkommende Frage, wo sich im Rahmen der neuen Begebenheiten der Aufenthaltsort des Kindes befinden soll, ist ausgerichtet am Kindeswohl zu beantworten (vgl. <ref-law>; Botschaft, BBl 2011 9108). Dieser Grundsatz geniesst Verfassungsrang (<ref-law>) und bildet für sämtliche Kindesbelange die oberste Richtschnur (<ref-ruling> E. 3.4.2 S. 255; <ref-ruling> E. 4.2.4 S. 319; <ref-ruling> E. 5.4 S. 340). Entsprechend liess sich die Rechtsprechung in Bezug auf die Relocation eines Kindes bereits unter dem alten Recht von der Maxime des Kindeswohls leiten (vgl. <ref-ruling> E. 3.3 S. 358 im Zusammenhang mit einem beabsichtigten Wegzug nach Tschechien). Sie bildet auch in den umliegenden Ländern die Richtschnur für die Ausgestaltung der Eltern-Kind-Beziehung und die Frage des Aufenthaltsortes, dessen Verlegung bei Uneinigkeit der Eltern der richterlichen Entscheidung bedarf (Deutschland: vgl. in E. 2.5 zitierte Rechtsprechung; Frankreich: Art. 373-2 Abs. 3 CCfr, Entscheid der Cour de cassation Nr. 06-17869 vom 13. März 2007; Italien: Regelung in Art. 337ter und 337sexies CCit, insb. Art. 337ter Abs. 2 CCit; Österreich: Regelung in § 162 ABGB, insb. § 162 Abs. 3 ABGB).
Die vom Gericht oder der Kindesschutzbehörde zu beantwortende Frage lautet folglich nicht, ob es für das Kind vorteilhafter wäre, wenn beide Elternteile im Inland verbleiben würden. Die entscheidende Fragestellung ist vielmehr, ob sein Wohl besser gewahrt ist, wenn es mit dem auswanderungswilligen Elternteil wegzieht oder wenn es sich beim zurückbleibenden Elternteil aufhält (vgl. COESTER-WALTJEN, a.a.O., S. 314), wobei diese Frage unter Berücksichtigung der auf <ref-law> gestützten Anpassung der Kinderbelange (Betreuung, persönlicher Verkehr, Unterhalt) an die bevorstehende Situation zu beantworten ist. Zwischen der Anpassung der Kinderbelange und der unter dem Aspekt des Kindeswohls zu beantwortenden Frage, ob die Verlegung des Aufenthaltsortes zu bewilligen ist, besteht nämlich eine enge Interdependenz (dazu E. 2.8).
2.7. Zu untersuchen ist im Folgenden, anhand welcher Kriterien die Frage des Kindeswohls zu prüfen ist.
Unter altem Recht hat das Bundesgericht diesbezüglich an die Rechtsprechung betreffend die Zuteilungskriterien im Trennungs- oder Scheidungsfall angeknüpft und - im Zusammenhang mit einem beabsichtigten Wegzug der Mutter auf die Philippinen und einem angekündigten Stellenantritt des Vaters in Singapur - erwogen, dass für die Neuregelung der Eltern-Kind-Verhältnisse die Interessen der Eltern in den Hintergrund zu treten hätten; abzustellen sei auf die persönlichen Beziehungen zwischen Eltern und Kindern, auf ihre erzieherischen Fähigkeiten und die Bereitschaft, die Kinder in eigener Obhut zu haben und sie weitgehend persönlich zu betreuen und zu pflegen, sowie auf das Bedürfnis der Kinder nach der für eine harmonische Entfaltung in körperlicher, seelischer und geistiger Hinsicht notwendigen Stabilität der Verhältnisse, welches bei gleicher Erziehungs- und Betreuungsfähigkeit besonderes Gewicht erhalte (Urteil 5A_375/2008 vom 11. August 2008 E. 2).
Diese Kriterien können auf die Anwendung von <ref-law> übertragen werden. Weil es in der Regel um eine Anpassung der bestehenden Regelung an die neue Situation geht (vgl. <ref-law>), wird das bisher gelebte Betreuungsmodell faktisch den Ausgangspunkt der Überlegungen bilden. Sind die Kinder bislang von beiden Elternteilen weitgehend zu gleichen Teilen betreut worden (geteilte bzw. alternierende Obhut) und sind beide Teile weiterhin willens und in der Lage, persönlich oder im Rahmen eines im Kindeswohl liegenden Betreuungskonzeptes für das Wohl der Kinder zu sorgen, so ist die Ausgangslage gewissermassen neutral. Diesfalls ist anhand weiterer Kriterien (wie familiäres und wirtschaftliches Umfeld, Stabilität der Verhältnisse, Sprache und Beschulung, gesundheitliche Bedürfnisse, Meinungsäusserung älterer Kind) zu eruieren, welche Lösung im besten Interesse des Kindes liegt.
War hingegen der wegzugswillige Elternteil nach dem bisher tatsächlich gelebten Betreuungskonzept ganz oder überwiegend die Bezugsperson (namentlich beim klassischen Besuchsrechtsmodell), wird es tendenziell zum besseren Wohl der Kinder sein, wenn sie bei diesem verbleiben und folglich mit ihm wegziehen. Die für einen Verbleib der Kinder in der Schweiz notwendige Umteilung an den anderen Elternteil - welche ohnehin voraussetzt, dass dieser fähig und bereit ist, die Kinder bei sich aufzunehmen und für eine angemessene Betreuung zu sorgen - bedarf jedenfalls der sorgfältigen Prüfung, ob sie tatsächlich dem Kindeswohl entspricht.
Dabei kommt es wiederum auf die Umstände des Einzelfalles an. Sind die Kinder noch klein und dementsprechend mehr personen- denn umgebungsbezogen, ist eine Umteilung an den zurückbleibenden Elternteil angesichts des Grundsatzes der Betreuungs- und Erziehungskontinuität nicht leichthin vorzunehmen. Hingegen werden bei älteren Kindern zunehmend die Wohn- und Schulumgebung sowie der sich ausbildende Freundeskreis wichtig und vielleicht haben sie schon eine Lehrstelle in Aussicht; hier könnte der Verbleib in der Schweiz, soweit eine Umplatzierung zum anderen Elternteil möglich ist, dem Kindeswohl unter Umständen besser dienen.
Zu beachten sind auch alle weiteren Facetten der konkreten Situation. Beispielsweise ist es für ein Kind nicht dasselbe, ob es bereits bislang zweisprachig aufgewachsen ist oder ob es neu in einer ihm fremden Sprache beschult würde, und es ist mit Blick auf die Stabilität der Verhältnisse auch nicht dasselbe, ob beispielsweise der auswanderungswillige Elternteil in sein Heimatland bzw. in den angestammten Familienkreis (dem Kind bereits vertraute Grosseltern, Onkeln und Tanten etc.) zurückkehrt bzw. zu einem neuen Partner in ein wirtschaftlich und sozial abgesichertes Umfeld zieht oder ob es beispielsweise um Gewinnung von Abstand bzw. um Abenteuerlust und eine Lebensführung mit weitgehend offener Perspektive geht. Schliesslich wird bei älteren Kindern massgeblich auch auf die bei ihrer Anhörung geäusserten Wünsche und Vorstellungen abzustellen sein, soweit sich diese mit den konkreten Begebenheiten (tatsächliche Aufnahme- und Betreuungsmöglichkeiten des betreffenden Elternteils) vereinbaren lassen.
Zusammenfassend ergibt sich, dass für die Beurteilung des Kindeswohls immer die konkreten Umstände des Einzelfalles massgeblich sind, indes dem wegzugswilligen Elternteil, welcher die Kinder bislang überwiegend betreut hat und dies auch in Zukunft tun wird, die Verlegung des Aufenthaltsortes der Kinder ins Ausland in der Regel zu bewilligen sein wird, wovon übereinstimmend auch die Lehre ausgeht (vgl. BUCHER, Elterliche Sorge, in: Familien in Zeiten grenzüberschreitender Beziehungen, Freiburg 2013, S. 63; CANTIENI/BIDERBOST, Reform der elterlichen Sorge aus Sicht der Kindes- und Erwachsenenschutzbehörde (KESB) - erste Erfahrungen und Klippen, in: FamPra.ch 2015, S. 792; BÜCHLER/MARANTA, Das neue Recht der elterlichen Sorge, in: Jusletter vom 11. August 2014, Rz. 84 f.; FASSBIND, a.a.O., S. 697; wohl gl.M. SCHWENZER/COTTIER, in: Basler Kommentar, N. 14 f. zu <ref-law>).
In der Praxis wird der zurückbleibende Elternteil oft den Einwand erheben, dass der andere Teil mit dem Auswanderungswunsch das Ziel verfolge, ihm die Kinder zu entziehen und insofern ein rechtsmissbräuchliches Verhalten vorliege, welches nicht geschützt werden dürfe. Solche Fälle können vorkommen, sie dürften aber selten sein (vgl. BUCHER, a.a.O., S. 63 unten). Es ist nachvollziehbar, dass dies dem zurückbleibenden Elternteil subjektiv anders vorkommen mag, denn die Aufrechterhaltung des Kontaktes zum Kind wird schwieriger und oftmals ist der geplante Wegzug die Folge der elterlichen Trennung, welche ihrerseits die Folge von Spannungen und Schwierigkeiten auf der Elternebene ist. Indes entspricht es keiner verbreiteten Realität, dass ein Elternteil ins Nichts wegzieht. Vielmehr ist im Zielland in der Regel eine ökonomische Basis oder Aussicht vorhanden und gibt es handfeste Gründe für den Wegzug wie beispielsweise die Rückkehr ins Heimatland oder den eigenen Familienkreis, das Zusammenziehen mit einem neuen Partner oder ein karriereförderndes Stellenangebot.
Sind aber tatsächlich keine plausiblen Gründe ersichtlich und zieht ein Elternteil offensichtlich nur weg, um das Kind dem anderen Elternteil zu entfremden, ist die Bindungstoleranz und damit Erziehungsfähigkeit des betreffenden Elternteils in Frage gestellt mit der Folge, dass die Umteilung des Kindes in Erwägung zu ziehen ist (vgl. <ref-ruling> E. 3.3 S. 359; Urteil 5A_923/2014 vom 27. August 2015 E. 5.1, nicht publ. in: <ref-ruling>; vgl. sodann Urteil 5A_202/2015 vom 26. November 2015 E. 3.4 a.E., zur Publ. bestimmt; siehe auch den vorstehend zitierten BGH-Entscheid XII ZB 81/09 vom 28. April 2010). Insofern können die Auswanderungsmotive beschränkt auf Einzelfälle indirekt doch eine Rolle spielen. Auch in solchen Konstellationen setzt freilich die Umteilung der Kinder an den anderen Elternteil voraus, dass dieser erziehungsfähig ist und er die Kinder tatsächlich bei sich aufnehmen und betreuen kann.
2.8. Aus dem gesetzlichen Konzept ergibt sich, dass das Gericht bzw. die Kindesschutzbehörde - mit Wirkung ab dem tatsächlichen Wegzug des auswandernden Elternteils - soweit nötig die Betreuungs-, Besuchsrechts- und Unterhaltsregelung anzupassen hat (vgl. <ref-law>), und zwar gegebenenfalls auch für den Fall eines negativen Entscheides, d.h. wenn das Kind in der Schweiz verbleibt und der auswandernde Elternteil alleine wegzieht. Materiell bildet die Regelung im Sinn von <ref-law> einen notwendigen Bestandteil des Entscheides über den Wegzug, weil nach dem Gesagten die konkrete Ausgestaltung der Betreuung und des persönlichen Verkehrs die Frage beeinflusst, welchen Aufenthaltsort das Kind in seinem besten Interesse haben soll. Im internationalen Verhältnis lassen sich diese Fragen auch aus prozessualen Gründen schlecht abspalten, weil mit dem Wegzug des Kindes in der Regel die schweizerische Entscheidzuständigkeit in Bezug auf die Ausgestaltung der Eltern-Kind-Beziehung verloren geht (vgl. <ref-law> und ferner Art. 5 Ziff. 2 lit. a und c LugÜ). In der Botschaft wurde die Zustimmungsbedürftigkeit für den Wegzug des Kindes ins Ausland gerade mit dem Wechsel der Jurisdiktion begründet (BBl 2011 9108). Die legislatorischen Motive würden unterlaufen, wenn ausschliesslich über die Frage des Wegzuges des Kindes befunden und dem zurückbleibenden Elternteil zugemutet würde, notwendige Anpassungen in Bezug auf die Eltern-Kind-Beziehung im Ausland einzuklagen.
Was die konkrete Regelung der Kinderbetreuung und Ausgestaltung des persönlichen Verkehrs anbelangt, ist vorauszuschicken, dass oft kein Idealzustand zu erreichen sein wird, und zwar unabhängig davon, ob das Kind wegzieht oder ob es in der Schweiz verbleibt. Gerade bei grösseren Distanzen sind Modelle mit geteilter Betreuung unmöglich und wird auch die Frequenz und Intensität von Besuchen zwangsläufig nicht in gleichem Umfang aufrechterhalten werden können. Angesichts des zeitlichen und finanziellen Aufwandes für die Ausübung des persönlichen Verkehrs sowie unter Berücksichtigung der Bedürfnisse der Kinder wird die Neuregelung bei grösseren Distanzen meist darauf hinauslaufen, dass eine kleinere Kadenz von Wochenendbesuchen durch längere einzelne Wochenendeinheiten und/oder längere Ferienaufenthalte (teil-) kompensiert wird (vgl. <ref-ruling> E. 3.3 S. 359). Indes wären bei Kleinkindern - bei welchen sich der physische Kontakt auch nicht hinreichend mit anderen Kommunikationskanälen wie Skype substituieren lässt - eigentlich häufige und kurze Besuchsintervalle ohne Übernachtungen ideal (GLOOR/SIMONI, Wohnortswechsel mit Kinder nach Trennung und Scheidung, Siebte Schweizer Familienrecht§Tage 2014, S. 251).
In dieser Situation sind die Gerichte gehalten, eine der neuen Situation angepasste Betreuungs- und Kontaktregelung zu treffen, welche verbindlich und durchsetzbar ist und mit welcher der konventionsrechtlichen Vorgabe von Art. 9 Abs. 3 der UN-Kinderrechtskonvention (KRK, SR 0.107) nachgelebt wird. Diese sieht vor, dass ein jeder Vertragsstaat das Recht des von einem oder beiden Elternteilen getrennten Kindes achtet, regelmässige persönliche Beziehungen und unmittelbare Kontakte zu beiden Elternteilen zu pflegen. Es entspricht sodann kinderpsychologischer Erkenntnis, dass aufgrund des schicksalhaften Eltern-Kind-Verhältnisses die Beziehung des Kindes zu beiden Elternteilen wichtig ist und bei dessen Identitätsfindung eine entscheidende Rolle spielen kann (<ref-ruling> E. 2.2.2 S. 590; <ref-ruling> E. 4 S. 211 f.). Deshalb haben im Übrigen beide Elternteile mit Blick auf das Wohl des Kindes die Pflicht, eine gute Beziehung zum jeweils anderen Elternteil zu fördern; namentlich hat der hauptbetreuende Elternteil das Kind positiv auf Besuche, auf Skype-Kontakte, etc. beim oder mit dem anderen Elternteil vorzubereiten (Urteil 5A_202/2015 vom 26. November 2015 E. 3.4, zur Publ. bestimmt; Urteil 5A_505/2013 vom 20. August 2013 E. 6.3).
Weil der behördliche Entscheid über die Aufenthaltsverlegung und die Anpassung der Eltern-Kind-Beziehung eine Einheit bilden, ist auch klar, dass es nicht abstrakt um einen Wegzug aus der Schweiz, sondern immer konkret um eine Übersiedelung in eine bestimmte Gegend und in ein bestimmtes Umfeld geht. Es ist für die Frage des Kindeswohls und die Neugestaltung des persönlichen Verkehrs nicht einerlei, ob ein Wegzug in einen benachbarten oder in einen entlegenen Staat geplant ist. Es ist aber auch nicht einerlei, ob ein Wegzug von Basel nach Lörrach oder nach Berlin zur Debatte steht. Im einen Fall könnte sogar das Modell einer geteilten Obhut aufrechterhalten oder eingerichtet werden, während im anderen Fall ganz andere Lösungen gefragt sind. Selbstredend können vom auswanderungswilligen Elternteil nicht Details wie genaue Wohn- und Schuladresse etc. verlangt werden, weil dieser für die Umsetzung seiner Pläne oft auf den bewilligenden Behördenentscheid angewiesen sein wird. Indes müssen die Konturen des Wegzuges feststehen, weil die Zustimmung des anderen Elternteils bzw. der behördliche Entscheid, mit welchem die Zustimmung des anderen Elternteils substituiert werden soll, auf konkreten Grundlagen fussen muss. In diesem Zusammenhang ist auch zu bedenken, dass der auswandernde Elternteil, welchem die Verlegung des Aufenthaltsortes der Kinder bewilligt wird, nur dann vor einem Rückführungsverfahren sicher sein kann, wenn sich der bewilligende Entscheid auf einen konkreten Umzug bezieht.
2.9. Im vorliegenden Fall stellt der Beschwerdeführer fast ausschliesslich die Motive der Mutter für den von ihr beabsichtigten Wegzug in Frage. Nach dem Gesagten unterliegen diese aber nicht der gerichtlichen Überprüfung. Insofern geht auch das Eventualbegehren um Rückweisung an das Kantonsgericht zu näheren diesbezüglichen Abklärungen fehl.
Was die Frage des Kindeswohles anbelangt, kann das sinngemässe Vorbringen, dass den Kindern in Graz Gefahren drohen, nicht ernsthaft sein. Die Lebensqualität in Graz ist vergleichbar mit derjenigen in U._, die Kinder werden in der gleichen Sprache beschult und sie sind in einem Alter, in welchem sie sich am neuen Ort umgehend einleben werden. Sie können in Graz ebenso glücklich aufwachsen wie in der Schweiz.
Dass der persönliche Verkehr weniger häufig wird stattfinden können und für alle Beteiligten mit erhöhtem Aufwand verbunden ist, trifft zu. Dies ist aber für sich genommen kein Grund, den Wegzug der Kinder zu verbieten. Unzutreffend ist sodann die Behauptung, mit dem Wegzug werde das Kontaktrecht verunmöglicht (Beschwerde, S. 15 unten) und komme es zu einer sofortigen Entfremdung der Kinder (Beschwerde, S. 18), erlaubt doch die kantonale Besuchsrechtsregelung monatliche Kontakte und damit das Aufrechterhalten einer tragfähigen Beziehung.
All diese Elemente sind vorliegend ohnehin wenig entscheidtragend insofern, als der Vater auch für die Zukunft ausdrücklich ausschliesst, die Kinder selbst zu betreuen (angefochtenes Urteil, S. 12; Beschwerde, S. 15), und er sich darauf beschränkt, ein umfangreicheres Besuchsrecht zu verlangen (dazu im Einzelnen E. 3). Damit ist die Sachverhaltsbehauptung, es sei völlig unbelegt, dass er die Erziehung und Alltagsbetreuung seit jeher der Mutter überlassen hätte (Beschwerde, S. 14), mit Blick auf den zutreffenden Entscheid ebenso unerheblich wie die Beanstandung in Bezug auf die Beweiswürdigung zum Vater-Kinder-Verhältnis (Beschwerde, S. 15). In rechtlicher Hinsicht ist der Entscheid, wo sich der gewöhnliche Aufenthalt der Kinder befinden soll, imperativ präjudiziert, wenn nur ein Elternteil bereit ist, die Betreuung der Kinder zu übernehmen, denn eine nähere Diskussion des Kindeswohls läuft bei dieser Ausgangslage letztlich ins Leere (vgl. E. 2.7).
Angesichts der Tatsache, dass nur die Mutter bereit ist, die Kinder überwiegend zu betreuen, und im Übrigen die kantonalen Gerichte eine situationsadäquate Lösung in Bezug auf die Neugestaltung des persönlichen Verkehrs für die Zeit ab dem Wegzug nach Graz gefunden haben (dazu E. 3), ist die Erlaubnis, den Aufenthaltsort der Kinder dorthin zu verlegen, bundesrechtskonform.
3.
Strittig ist ferner die Ausgestaltung des Rechtes auf persönlichen Verkehr zwischen Vater und Kindern. Es geht dabei um die Anwendung von <ref-law> und für die Zeit ab dem Wegzug nach Graz um die Anwendung von Art. 273 Abs. 1 i.V.m. <ref-law>.
3.1. Das Kantonsgericht hat in diesem Zusammenhang festgehalten, dass die Ausübung des Besuchsrechts nach anfänglichen Schwierigkeiten mittlerweile gut klappe und auf Seiten der Mutter auch die nötige Bindungstoleranz vorhanden sei. Angesichts des Alters der Kinder wären häufige und kurze Besuche ideal, was sich aber bei einem Wegzug nach Graz angesichts der Distanz so nicht mehr umsetzen lasse. Die erstinstanzliche Regelung, wonach der Vater nebst zwei Wochen Ferien einmal pro Monat für ein Wochenende nach Graz fahre und die Mutter die Kinder viermal pro Jahr für ein Wochenende nach U._ bringe, sei angemessen. Der Wunsch des Vaters nach mehr persönlichem Umgang sei achtenswert; seine Vorstellungen, wie solche Kontakte auszusehen hätten (namentlich sämtliche Feiertage bei ihm und insgesamt sieben Wochen Ferien), zeugten aber von wenig Gespür für die Bedürfnisse der Kinder. Diese möchten Feiertage auch mit der Mutter verbringen und es werde ihnen angesichts des Alters mit der quartalsweisen Reise in die Schweiz (zuzüglich Reisen im Zusammenhang mit den Ferien) bereits genug zugemutet. Wenn die Kinder grösser seien, könnte eine Ausdehnung insbesondere des Ferienrechts angezeigt sein, aber das lasse sich heute noch nicht mit genügender Klarheit voraussagen.
3.2. Was den Sachverhalt anbelangt, macht der Beschwerdeführer geltend, es sei nicht belegt, dass das Besuchsrecht gut funktioniere (Beschwerde, S. 11), um gleichzeitig auszuführen, die Ausübung des Besuchsrechts funktioniere inzwischen und die Kinder würden bei ihm auch übernachten (Beschwerde, S. 17 unten). Unbekümmert um die Widersprüchlichkeit der Aussagen handelt es sich ohnehin um appellatorische Ausführungen; mangels tauglicher Willkürrügen ist die kantonale Sachverhaltsfeststellung, dass der persönliche Verkehr gut klappe, für das Bundesgericht verbindlich (vgl. E. 1).
3.3. In rechtlicher Hinsicht gilt der Grundsatz, dass für die Ausgestaltung des persönlichen Verkehrs das Kindeswohl im Vordergrund steht und allfällige Interessen der Eltern zurückzutreten haben (vorstehend E. 2.7; sodann <ref-ruling> E. 3b S. 451; <ref-ruling> E. 2.1 S. 587 f.; Urteile 5A_381/2010 vom 21. Juli 2010 E. 5.3.2; 5A_79/2014 vom 5. März 2015 E. 4.1). Welche Ordnung des persönlichen Verkehrs zwischen Eltern und Kindern angemessen ist, lässt sich nicht objektiv und abstrakt umschreiben, sondern entscheidet sich im konkreten Einzelfall nach gerichtlichem Ermessen (Urteile 5A_72/2011 vom 22. Juni 2011 E. 4.1; 5A_432/2011 vom 20. September 2011 E. 2.5). Immerhin hat der persönliche Verkehr in den vergangenen Jahren eine zunehmende Ausdehnung erfahren (vgl. <ref-ruling> E. 2.1 S. 587; <ref-ruling> E. 2.3 S. 320; Urteil 5A_79/2014 vom 5. März 2015 E. 4.2), wobei innerschweizerisch ein gewisses Gefälle dahingehend auszumachen ist, dass die Besuchsrechtsregelungen von Osten gegen Westen grosszügiger werden (vgl. BGE <ref-ruling> E. 2.3 S. 320). Die allgemeine Tendenz zur Ausweitung des Besuchsrechtes fusst auf der Erkenntnis, dass der Kontakt zum getrennt lebenden Elternteil für das Kind von grosser Bedeutung ist (<ref-ruling> E. 2.2.2 S. 590; <ref-ruling> E. 4 S. 211 f.) und dadurch namentlich auch die Scheidungsverarbeitung erleichtert und langfristig die Persönlichkeitsentwicklung des Kindes gefördert wird (BGE <ref-ruling> E. 2.3 S. 320).
In prozessualer Hinsicht ist zu beachten, dass es um Ermessensentscheide geht, bei deren Überprüfung das Bundesgericht eine gewisse Zurückhaltung übt (BGE <ref-ruling> E. 3 S. 210; Urteile 5A_694/2014 vom 24. März 2015 E. 4; 5A_79/2014 vom 5. März 2015 E. 4.3). Allerdings darf das kantonale Gericht zur Begründung einer bestimmten Regelung nicht einfach pauschal auf eine standardisierte Praxis verweisen (vgl. <ref-ruling> E. 3b S. 451; <ref-ruling> E. 2.1 S. 587 f.; Urteil 5A_79/2014 vom 5. März 2015 E. 4.3).
3.4. Für die Zeit des Aufenthaltes in der Schweiz verlangt der Beschwerdeführer, dass die Besuchswochenenden bereits am Freitagabend und nicht erst am Samstagmorgen beginnen. Selbst bzw. gerade für den Fall, dass der Wegzug nach Graz bewilligt würde, erachtet er dies als wichtig, weil dann die Besuchsrechtswochenenden jeweils auch länger wären und die Kinder bereits darauf vorbereitet werden könnten.
In Bezug auf den Beginn der Besuchswochenenden kann schweizweit ebenfalls ein klarer Trend zur Ausdehnung auf Freitagabend festgestellt werden. Zumal die Kinder noch recht klein sind, ist aber für die Zeit, während der sie sich in U._ aufhalten, eine Ausdehnung auf Freitagabend nicht zwingend erforderlich, weil die Besuche hier 14-täglich und somit in grösserer Frequenz als beim Wegzug nach Graz erfolgen; jedenfalls lässt sich nicht geradezu sagen, die kantonalen Gerichte hätten das ihnen zustehende Ermessen überschritten.
3.5. Nicht klar ist, ob der Beschwerdeführer für den Fall des Wegzuges nach Graz in der Beschwerdebegründung ebenfalls eine Ausdehnung des Besuchsrechtes verlangt; er scheint dies für gegenstandslos zu halten, weil ohnehin keine Erlaubnis zu erteilen sei (Beschwerde, S. 18). Jedenfalls ist das von ihm gestellte Rechtsbegehren Ziff. 3, mit welchem er ein Besuchsrecht an jedem zweiten Wochenende verlangt, offensichtlich auf den Fall ausgerichtet, dass die Kinder ihren gewöhnlichen Aufenthalt in U._ haben. Der Beschwerdeführer müsste ein spezifisches Rechtsbegehren für den Wegzugsfall stellen und dieses auch konkret begründen. Indem er dies nicht tut, ist auf die Beschwerde insoweit nicht einzutreten.
Der Vollständigkeit halber sei erwähnt, dass einem allfälligen Vorbringen um Ausdehnung ohnehin kein Erfolg beschieden sein könnte. Die kantonalen Instanzen haben für die Zeit, ab der sich die Kinder in Graz aufhalten werden, eine angesichts der Distanz, der konkreten Reiseverbindungen und des Alters der Kinder vernünftige und tragfähige Lösung gefunden, auch was die Verteilung der Reiselasten für die Elternteile und die Kinder anbelangt.
3.6. Unabhängig von der Frage des Aufenthaltsortes der Kinder kritisiert der Beschwerdeführer schliesslich den Entscheid in Bezug auf die Regelung für die Feiertage. Es sei willkürlich, wenn das Kantonsgericht einerseits eine alternierende Regelung für die Feiertage als üblich bezeichne, ihm aber schliesslich an den Feiertagen überhaupt keinen persönlichen Verkehr zugestehe.
Das Kantonsgericht hat ein zusätzliches Besuchsrecht nicht ohne Begründung, sondern damit abgelehnt, dass insgesamt die langen Reisewege für die Kinder eine Belastung darstellten und es damit ein Bewenden haben müsse, dass sie die Reise jeden dritten Monat auf sich nehmen müssten, zumal auch noch das Ferienrecht hinzukomme (angefochtener Entscheid, S. 16).
Diese Begründung hat ihre Berechtigung. Andererseits ist es auch wichtig, dass der zurückbleibende Elternteil nicht vollständig davon ausgeschlossen ist, mit seinen Kindern hohe Feiertage zu verbringen. Dies trifft insbesondere auf Weihnachten zu, wo ein Familienerlebnis und das Zelebrieren von Ritualen wie der persönliche Austausch von Geschenken ermöglicht werden sollte, soweit nicht zwingende Gründe entgegen stehen. In diesem Sinn scheint es angebracht, in teilweiser Gutheissung des betreffenden Begehrens und Ergänzung der kantonalen Regelung ein verlängertes Wochenende alternierend an Ostern und Auffahrt (angesichts der Distanzen nicht aber zusätzlich an Pfingsten) sowie einen Besuch alternierend am Heiligabend und am Weihnachtsabend (je mit Folgetag) festzusetzen, wobei nach dem Weggang der persönliche Verkehr an Weihnachten stets in Graz stattzufinden hat; es wäre den Kindern nicht zuzumuten, die Weihnachtstage anteilsmässig an zwei entfernten Orten zu verbringen.
4.
Zusammenfassend ergibt sich, dass die Beschwerde im soeben genannten Umfang gutzuheissen, im Übrigen aber abzuweisen ist, soweit auf sie eingetreten werden kann. Ferner ist beiden Parteien die unentgeltliche Rechtspflege zu gewähren, je unter Beigabe der sie vertretenden Rechtsanwältinnen (Art. 64 Abs. 1 und 2 BGG). Angesichts des Ausgangs des Verfahrens rechtfertigt es sich, die Gerichtskosten des bundesgerichtlichen Verfahrens zu 7/10 dem Beschwerdeführer und zu 3/10 der Beschwerdegegnerin aufzuerlegen (<ref-law>), je unter Vorbehalt der unentgeltlichen Rechtspflege, aber die Kostenverteilung für das kantonale Verfahren unverändert zu belassen. Ferner sind für das bundesgerichtliche Verfahren beide Anwältinnen aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
In teilweiser Gutheissung der Beschwerde und entsprechender Modifikation von Ziff. 2 des Entscheides des Kantonsgerichtes St. Gallen vom 29. April 2015 wird der Entscheid des Kreisgerichtes St. Gallen vom 7. Juli 2014 im Sinn einer zusätzlichen Dispositivziffer 4c um folgende Anordnung ergänzt:
Dem Vater einerseits und den Kindern C._ und D._ andererseits steht das Recht zu, folgende Zeiten miteinander zu verbringen: in den ungeraden Jahren an Ostern (jeweils von Donnerstagabend, 18.00 Uhr, bis Montagabend, 18.00 Uhr) und Weihnachten (jeweils vom 24. Dezember, 14.00 Uhr, bis 25. Dezember, 18.00 Uhr) sowie in den geraden Jahren am Auffahrtswochenende (jeweils von Mittwochabend, 18.00 Uhr, bis Sonntagabend, 18.00 Uhr) und an Weihnachten (jeweils vom 25. Dezember, 14.00 Uhr, bis 26. Dezember, 19.00 Uhr). Halten sich die Kinder gewöhnlich in Graz auf, ist das Besuchsrecht an Weihnachten in Graz auszuüben.
Im Übrigen wird die Beschwerde abgewiesen, soweit auf sie einzutreten ist.
2.
Beiden Parteien wird die unentgeltliche Rechtspflege gewährt, je unter Beiordnung der sie vertretenden Rechtsanwälte.
3.
Die Gerichtskosten von Fr. 2'000.-- werden zu 7/10 dem Beschwerdeführer und zu 3/10 der Beschwerdegegnerin auferlegt, jedoch einstweilen auf die Bundesgerichtskasse genommen.
4.
Die Rechtsanwältinnen Dr. iur. Monika Brenner und Denise Dornier-Zingg werden für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse je mit Fr. 3'000.-- entschädigt.
5.
Dieses Urteil wird den Parteien und dem Kantonsgericht St. Gallen, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 11. März 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Möckli